Đua xe địa hình (Câu 3 đề thi Olympic 27 tháng 4 HSG lớp 10, 11 tỉnh BR-VT 2022-2023)


Submit solution

Points: 50
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Năm 2021 Việt Nam lần đầu tiên tổ chức cuộc đua xe địa hình tại Đồng Mô (Hà Nội) với số lượng thành viên tham gia là \(n\). Theo luật đua xe hơi địa hình, mỗi xe có 2 người tham gia. Trước khi tham gia người chơi phải đăng ký hồ sơ năng lực với ban tổ chức là một số nguyên dương \(a_i\) (\(a_i\) càng lớn thì năng lực càng cao). Để các xe có sự cân bằng về năng lực người chơi, mỗi vòng đua ban tổ chức sẽ đưa ra \(k\) độ chênh lệch về hồ sơ năng lực. Các xe có \(k\) độ lệch cùng nhau thì mới được tham gia vòng đua.

Yêu cầu: Hãy giúp ban tổ chức chọn các cặp đua có độ chênh lệch \(k\) cùng nhau nhiều nhất có thể.

Dữ liệu vào:

  • Dòng 1: chứa hai số nguyên dương \(n\) và \(k\) \((1 \le n \le 10^5, 2 \le k \le 10^9)\);
  • Dòng 2: ghi \(n\) số nguyên dương \(a_1, a_2,..., a_n (a_i \le 10^9)\)

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là kết quả bài toán.

Ví dụ:

INPUT OUTPUT
\(6\) \(2\)
\(3\) \(5\) \(5\) \(5\) \(10\) \(7\)
\(6\)

Giải thích: Có 6 cặp đua thỏa mãn điều kiện (3, 5), (3, 5), (3, 5), (7, 5), (7, 5), (7, 5)

Ràng buộc:

  • Subtask 1: (có 60% số test) \(1 < n \le 10^3; 2 \le k \le 10^3\);
  • Subtask 2: (có 20% số test) \(10^3 < n \le 10^4; 2 \le k \le 10^5\);
  • Subtask 3: (có 20% số test) \(10^4 < n \le 10^5; 2 \le k \le 10^9\);

Comments

There are no comments at the moment.