Elearning CodePath – CTP Online Judge

Khiêu Vũ

KHIEUVU

🟢 Hard #Hash #Combinatorics

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho $N$ người tham gia buổi tiệc khiêu vũ, với chiều cao lần lượt là $h_1, h_2, \dots, h_n$.
Quy tắc: Chỉ những cặp đôi có chiều cao chênh lệch nhau đúng bằng số $K$ mới được khiêu vũ cùng nhau.

Yêu cầu: Hãy đếm xem có tất cả bao nhiêu cặp đôi $(i, j)$ thỏa mãn điều kiện, với $i \ne j$.
Điều kiện thỏa mãn là:
$|h_i - h_j| = K$

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `KHIEUVU.INP` gồm 2 dòng:

* Dòng đầu: Ghi 2 số nguyên $N$ (số lượng người) và $K$ (độ chênh lệch chiều cao yêu cầu), cách nhau bởi dấu cách.
* Dòng thứ 2: Ghi $N$ số $h_1, h_2, \dots, h_n$ là chiều cao của $N$ người tham gia buổi tiệc, cách nhau bởi dấu cách.

Giới hạn:
* $2 \le N \le 10^5$.
* $0 \le K \le 10^9$.
* $h_i \le 10^9$.

---
### 📤 Định dạng Đầu ra

Ghi vào file `KHIEUVU.OUT` một số duy nhất là kết quả của bài toán (số lượng cặp đôi).

---
### ✨ Ví dụ

| Input (`KHIEUVU.INP`) | Output (`KHIEUVU.OUT`) | Giải thích |
| :--- | :--- | :--- |
| `7 2` `10 7 5 12 1 9 8` | `4` | Các cặp đôi có độ chênh lệch chiều cao bằng $K=2$: * $(10, 8)$: $|10 - 8| = 2$ * $(7, 5)$: $|7 - 5| = 2$ * $(7, 9)$: $|7 - 9| = 2$ * $(12, 10)$: $|12 - 10| = 2$ (Lưu ý: Ví dụ giải thích gốc đề cập đến các chỉ số $(1, 4), (1, 7), (2, 3), (2, 6)$ tương ứng với các cặp giá trị: $(10, 12), (10, 8), (7, 5), (7, 9)$. Tổng cộng có 4 cặp). |

---
### 🏷 Ràng buộc

| Tỷ lệ điểm | Ràng buộc |
| :--- | :--- |
| $50\%$ | $N \le 10^3$; $h_i \le 10^6$ |
| $50\%$ | $N \le 10^5$; $h_i \le 10^9$ |

---

✅ Đã AC: 3 / 18 submissions