Đ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)

View as PDF

Submit solution

Points: 50.00
Time limit: 1.0s
Memory limit: 64M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
Assembly, Awk, Brain****, C, C++, Java, Pascal, Perl, Python, Sed, Text

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~;

Loading...