IOI 2012 - City
Xem PDFGiống nhiều nhà khoa học và nghệ sĩ Ý cùng thời, Leonardo rất quan tâm đến quy hoạch và thiết kế đô thị. Ông muốn xây dựng một thành phố lý tưởng: tiện nghi, rộng rãi và sử dụng tài nguyên hợp lý, tránh sự chật hẹp, tù túng của các thành phố thời Trung Cổ.
Thành phố lý tưởng
Thành phố gồm \(N\) khối đặt trên một lưới ô vuông vô hạn. Mỗi ô được xác định bởi cặp tọa độ (hàng, cột). Các ô kề với \((i,j)\) là \((i-1,j)\), \((i+1,j)\), \((i,j-1)\) và \((i,j+1)\). Mỗi khối phủ đúng một ô và chỉ có thể đặt tại \((i,j)\) khi \(1 \le i,j \le 2^{31}-2\). Tọa độ của một ô cũng được dùng để chỉ khối nằm trên ô đó. Hai khối kề nhau nếu nằm trên hai ô kề nhau.
Trong một thành phố lý tưởng, các khối liên thông và không có lỗ hổng bên trong đường biên. Cụ thể, phải thỏa mãn cả hai điều kiện:
- Với hai ô trống bất kỳ, tồn tại ít nhất một dãy các ô trống kề nhau nối chúng.
- Với hai ô không trống bất kỳ, tồn tại ít nhất một dãy các ô không trống kề nhau nối chúng.
Khi đi trong thành phố, một bước nhảy là di chuyển từ một khối sang khối kề nó; không được đi qua ô trống. Gọi \(v_0,v_1,\ldots,v_{N-1}\) là tọa độ các khối. Khoảng cách \(d(v_i,v_j)\) giữa hai khối khác nhau là số bước nhảy ít nhất để đi từ khối này đến khối kia.
Yêu cầu
Cho một thành phố lý tưởng, hãy tính tổng khoảng cách giữa mọi cặp khối \(v_i,v_j\) với \(i<j\):
Cài đặt chương trình con DistanceSum(N, X, Y), trong đó hai mảng \(X,Y\) đều có \(N\) phần tử; khối \(i\) ở tọa độ \((X[i],Y[i])\) với \(0 \le i \le N-1\). Vì kết quả có thể vượt quá khả năng biểu diễn bằng số nguyên \(32\) bit, hãy trả về tổng theo mô đun \(1\,000\,000\,000\) (một tỉ).
Chi tiết cài đặt
Nộp đúng một tệp city.c, city.cpp hoặc city.pas, cài đặt chương trình con với chữ ký sau.
C/C++
int DistanceSum(int N, int *X, int *Y);
Pascal
function DistanceSum(N : LongInt; var X, Y : array of LongInt) : LongInt;
Chương trình con phải hoạt động như đã mô tả. Bạn có thể cài đặt thêm các chương trình con dùng nội bộ. Bài nộp không được giao tiếp dưới bất kỳ hình thức nào với đầu vào/đầu ra chuẩn hoặc với bất kỳ tệp nào khác.
Dữ liệu vào
Trình chấm mẫu được cung cấp trong môi trường thi nhận dữ liệu theo định dạng:
- Dòng \(1\): \(N\).
- Các dòng \(2,\ldots,N+1\): mỗi dòng chứa
X[i] Y[i], theo thứ tự \(i=0,\ldots,N-1\).
Dữ liệu ra
Hàm DistanceSum trả về tổng khoảng cách giữa mọi cặp khối khác nhau, mỗi cặp tính một lần, theo mô đun \(1\,000\,000\,000\).
Ràng buộc
- \(1 \le X[i],Y[i] \le 2^{31}-2\) với \(0 \le i \le N-1\).
- Cấu hình là một thành phố lý tưởng theo cả hai điều kiện đã nêu.
- Giới hạn thời gian: \(1\) giây.
- Giới hạn bộ nhớ: \(256\) MiB.
Phân nhóm
| Phân nhóm | Điểm | Điều kiện |
|---|---|---|
| 1 | 11 | \(N \le 200\). |
| 2 | 21 | \(N \le 2\,000\). |
| 3 | 23 | \(N \le 100\,000\). Với hai ô có khối \(i,j\) bất kỳ mà \(X[i]=X[j]\), mọi ô nằm giữa chúng trên cùng hàng đều không trống. Đồng thời, với hai ô có khối \(i,j\) bất kỳ mà \(Y[i]=Y[j]\), mọi ô nằm giữa chúng trên cùng cột đều không trống. |
| 4 | 45 | \(N \le 100\,000\). |
Ví dụ
Ví dụ 1
Giải thích
Không cấu hình nào trong hình dưới đây là thành phố lý tưởng. Hai cấu hình đầu từ trái sang không thỏa mãn điều kiện thứ nhất; cấu hình thứ ba không thỏa mãn điều kiện thứ hai; cấu hình thứ tư không thỏa mãn cả hai điều kiện.
Ví dụ 2
Input
11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6Output
174Giải thích
Thành phố lý tưởng gồm \(N=11\) khối: \(v_0=(2,5)\), \(v_1=(2,6)\), \(v_2=(3,3)\), \(v_3=(3,6)\), \(v_4=(4,3)\), \(v_5=(4,4)\), \(v_6=(4,5)\), \(v_7=(4,6)\), \(v_8=(5,3)\), \(v_9=(5,4)\) và \(v_{10}=(5,6)\).
Chẳng hạn, \(d(v_1,v_3)=1\), \(d(v_1,v_8)=6\), \(d(v_6,v_{10})=2\) và \(d(v_9,v_{10})=4\). Có \(11 \times 10/2=55\) cặp khối; tổng khoảng cách của tất cả các cặp là \(174\).
Kỳ thi:
- IOI 2012 - Ngày 2 (27 Tháng 9., 2012)
Bình luận