Chia nhóm

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
huydong87
Dạng bài
Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: CAU2.INP Output: CAU2.OUT

Cho \(n\) số nguyên \(a_1, a_2, \ldots, a_n\). Người ta muốn chia \(n\) số nguyên này thành các nhóm, trong mỗi nhóm hiệu của số lớn nhất và số nhỏ nhất không vượt quá số nguyên dương \(h\) cho trước.
Yêu cầu: Xác định số lượng nhóm ít nhất khi chia nhóm \(n\) số nguyên đã cho thỏa mãn điều kiện trên.

Input

  • Dòng đầu chứa hai số nguyên dương \(n\) và \(h\), \(n \leq 10^{3}\), \(h \leq 10^{9}\).
  • Trong \(n\) dòng tiếp theo, dòng thứ i (1 ≤ i ≤ \(n\)) chứa số nguyên \(a_i\) có giá trị tuyệt đối không vượt quá \(10^{9}\).

Output

  • Số lượng nhóm ít nhất tìm được.

Example

Test 1

Input 
6 3
-7
27
-5
26
28
-6
Output 
2
Note

Có thể chia 6 số đã cho thành hai nhóm. Nhóm thứ nhất gồm các số thứ 1, thứ 3, thứ 6 và nhóm thứ hai là các số còn lại. Hai nhóm này đều có hiệu của số lớn nhất và số nhỏ nhất là 2, nhỏ hơn 3.

Bình luận