Điểm:
100 (p)
Thời gian:
1.5s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
\(n\) chiếc giày, chiếc thứ \(i\) có màu độ sáng \(s_i\) (\(1 \leq i \leq n\)), độ sáng càng lớn thì màu càng sáng.
Mỗi trận đấu lấy ra một đôi sử dụng, sau trận đấu đó, anh tháo giày và tặng lại cho các fan hâm mộ của mình. Hai chiếc giày mà anh chọn phải có độ sáng chênh lệch nhau không quá \(d\), tức là hai chiếc giày thứ \(i\) và \(j\) (\(i ≠ j\)) có thể được chọn nếu \(\lvert s_i - s_j \rvert \leq d\).
Em hãy viết chương trình tính giúp xem với \(n\) chiếc giày hiện có anh ấy sẽ chơi được tối đa bao nhiêu trận đấu.
Input
- Dòng đầu tiên chứa số tự nhiên \(n\) và \(d\) (\(n \leq 10^6, d \leq 10^9\)).
- Dòng tiếp theo chứa \(n\) só tự nhiên \(s_1, s_2, ..., s_n\) (\(s_i \leq 10^9\)).
Output
- In ra số trận đấu tối đa có thể chơi được.
Scoring
- Subtask \(1\) (\(25\%\) số điểm): \(d = 0, a_i \le 10 ^ {6}\)
- Subtask \(2\) (\(25\%\) số điểm): \(d = 0\)
- Subtask \(3\) (\(25\%\) số điểm): \(n \le 10 ^ {3}\)
- Subtask \(4\) (\(25\%\) số điểm): \(n \le 10 ^ {6}\)
Example
Test 1
Input
5 1
4 5 1 3 2
Output
2
Note
- Trận đấu thứ nhất \(\lvert 1 - 2 \rvert = 1 \leq 1\). mang chiếc giày thứ 3 và chiếc giày thứ 5, độ sáng chêch lệch là
- Trận đấu thứ hai \(\lvert 4 - 3 \rvert = 1 \leq 1\). mang chiếc giày thứ 1 vào chiếc giày thứ 4, độ sáng chêch lệch là
- Lúc này chỉ còn 1 chiếc giày nên không thể tham gia thi đấu tiếp được.
Bình luận
giàu thế nhờ con đại gia hay rì mà tận 1e6 chiếc giày =))
ác thật
5e5 đôi giày
tính 1 đôi 200k
5e5 * 200k = 100 000 000 000 (100 tỉ) oh shit =)
đấy là loại 200k =))
bthg giày ae chs bóng rổ cả triệu bạc cơ =))
x5 belike : 500 tỉ