2. IOI 2007 - Pairs
Mirko và Slavko đang chơi với những con thú đồ chơi. Trước tiên, họ chọn một trong ba bàn chơi trong hình dưới đây. Mỗi bàn gồm các ô (được vẽ bằng những vòng tròn trong hình), sắp xếp thành một lưới một chiều, hai chiều hoặc ba chiều.
Sau đó, Mirko đặt \(N\) con thú đồ chơi vào các ô.
Khoảng cách giữa hai ô là số bước ít nhất mà một con thú cần thực hiện để đi từ ô này đến ô kia. Trong một bước, con thú có thể đi sang một ô kề với ô hiện tại; các ô kề nhau được nối bằng những đoạn thẳng trong hình.
Hai con thú nghe thấy nhau nếu khoảng cách giữa hai ô của chúng không vượt quá \(D\). Nhiệm vụ của Slavko là tính số cặp con thú nghe thấy nhau.
Cho loại bàn chơi, vị trí của tất cả các con thú và số \(D\), hãy tính số cặp cần tìm.
Dữ liệu vào
Dòng thứ nhất chứa bốn số nguyên theo thứ tự:
- \(B\): loại bàn chơi.
- \(N\): số con thú.
- \(D\): khoảng cách lớn nhất mà hai con thú còn nghe thấy nhau.
- \(M\): kích thước bàn chơi, tức là giá trị tọa độ lớn nhất được phép xuất hiện trong dữ liệu vào.
Mỗi dòng trong \(N\) dòng tiếp theo chứa \(B\) số nguyên, cách nhau bởi dấu cách, là các tọa độ của một con thú. Mỗi tọa độ nằm trong đoạn từ \(1\) đến \(M\), kể cả hai đầu.
Có thể có nhiều con thú cùng nằm trong một ô.
Dữ liệu ra
Ghi một số nguyên duy nhất: số cặp con thú nghe thấy nhau.
Lưu ý: hãy dùng kiểu số nguyên \(64\) bit để tính toán và in kết quả (long long trong C/C++, int64 trong Pascal).
Ràng buộc
- \(1 \le B \le 3\).
- \(1 \le N \le 100\,000\).
- \(1 \le D \le 100\,000\,000\).
- Khi \(B=1\), \(1 \le M \le 75\,000\,000\).
- Khi \(B=2\), \(1 \le M \le 75\,000\).
- Khi \(B=3\), \(1 \le M \le 75\).
Chấm điểm trên hệ thống
Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.
Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.
Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.
| Nhãn nhóm | Điểm | Tệp dữ liệu vào gốc |
|---|---|---|
| 1 | 5 | pairs/pairs.in.1a, pairs/pairs.in.1b |
| 2 | 5 | pairs/pairs.in.2a |
| 3 | 7 | pairs/pairs.in.3a, pairs/pairs.in.3b |
| 4 | 8 | pairs/pairs.in.4a, pairs/pairs.in.4b |
| 5 | 8 | pairs/pairs.in.5a, pairs/pairs.in.5b, pairs/pairs.in.5c |
| 6 | 10 | pairs/pairs.in.6a, pairs/pairs.in.6b |
| 7 | 8 | pairs/pairs.in.7a, pairs/pairs.in.7b |
| 8 | 8 | pairs/pairs.in.8a, pairs/pairs.in.8b, pairs/pairs.in.8c, pairs/pairs.in.8d |
| 9 | 8 | pairs/pairs.in.9a, pairs/pairs.in.9b, pairs/pairs.in.9c, pairs/pairs.in.9d |
| 10 | 10 | pairs/pairs.in.10a, pairs/pairs.in.10b |
| 11 | 7 | pairs/pairs.in.11a, pairs/pairs.in.11b, pairs/pairs.in.11c |
| 12 | 8 | pairs/pairs.in.12a, pairs/pairs.in.12b, pairs/pairs.in.12c |
| 13 | 8 | pairs/pairs.in.13a, pairs/pairs.in.13b, pairs/pairs.in.13c |
Các ví dụ trong đề không tính điểm.
Ví dụ
Ví dụ 1
Input
1 6 5 100
25
50
50
10
20
23Output
4Note
Đánh số các con thú từ \(1\) đến \(6\) theo thứ tự xuất hiện trong dữ liệu vào. Bốn cặp nghe thấy nhau là:
- \(1\) và \(5\): khoảng cách \(5\).
- \(1\) và \(6\): khoảng cách \(2\).
- \(2\) và \(3\): khoảng cách \(0\).
- \(5\) và \(6\): khoảng cách \(3\).
Ví dụ 2
Input
2 5 4 10
5 2
7 2
8 4
6 5
4 4Output
8Note
Đánh số các con thú theo thứ tự xuất hiện trong dữ liệu vào. Tám cặp nghe thấy nhau là:
- \(1\) và \(2\): khoảng cách \(2\).
- \(1\) và \(4\): khoảng cách \(4\).
- \(1\) và \(5\): khoảng cách \(3\).
- \(2\) và \(3\): khoảng cách \(3\).
- \(2\) và \(4\): khoảng cách \(4\).
- \(3\) và \(4\): khoảng cách \(3\).
- \(3\) và \(5\): khoảng cách \(4\).
- \(4\) và \(5\): khoảng cách \(3\).
Ví dụ 3
Input
3 8 10 20
10 10 10
10 10 20
10 20 10
10 20 20
20 10 10
20 10 20
20 20 10
20 20 20Output
12
