Kỳ thi HSG THCS tỉnh Bắc Ninh 2025-2026

Oct 18, 2026, 03:00 – 06:30 (03:30:00) Concluded
Time Remaining 00:00:00
My Score
0 / 200
Rank
- / 2

D. XANHAT – Xa nhất

40 points 1.0 s 256 MB b09-stl-containers b12-greedy b14-twoptr data-structures greedy two-pointers

Cuộc thi Robocon 2030 dự kiến tổ chức cuộc thi nhảy xa trên cọc cho các chiến binh rô bốt. Ban tổ chức cuộc thi quy định luật chơi được mô tả như sau:

Trên sa bàn có $N$ cọc được sắp xếp trên một đường thẳng, các cọc được đánh số từ trái sang phải theo thứ tự từ $1$ đến $N$. Khoảng cách giữa các cọc liền kề là bằng nhau. Cọc thứ $i$ có chiều cao là $A_i$.

Ban tổ chức cho trước một số nguyên không âm $P$ làm điều kiện ràng buộc giữa chiều cao của cọc đích và chiều cao của cọc xuất phát.

Mỗi rô bốt khi tham gia cuộc thi được thực hiện một bước nhảy. Bước nhảy của rô bốt là $1$ lần nhảy từ cọc xuất phát $i$ bất kỳ đến cọc đích $j$ thỏa mãn các điều kiện:

  • $1 \le i \le j \le N$;
  • $A_j - A_i \ge P$.

Khi đó, giá trị $j - i$ được gọi là độ dài của bước nhảy. Bước nhảy xa nhất là bước nhảy có độ dài lớn nhất. Các rô bốt đạt bước nhảy xa nhất sẽ được quyền tham gia vòng chung kết của cuộc thi.

Ví dụ: Sa bàn có $6$ cọc với chiều cao $A = (4, 3, 7, 2, 6, 4)$ và $P = 3$. Các bước nhảy thỏa mãn gồm:

  • Nhảy từ cọc $1$ sang cọc $3$: độ dài $3 - 1 = 2$ ($A_3 - A_1 = 7 - 4 = 3 \ge 3$);
  • Nhảy từ cọc $2$ sang cọc $3$: độ dài $3 - 2 = 1$ ($A_3 - A_2 = 7 - 3 = 4 \ge 3$);
  • Nhảy từ cọc $2$ sang cọc $5$: độ dài $5 - 2 = 3$ ($A_5 - A_2 = 6 - 3 = 3 \ge 3$); $\rightarrow$ Bước nhảy xa nhất có độ dài là $3$.
Yêu cầu

Tìm độ dài bước nhảy xa nhất mà rô bốt có thể đạt được. Nếu không có bước nhảy nào thỏa mãn điều kiện thì in ra $0$.

Dữ liệu vào
  • Dòng 1: Ghi hai số nguyên $N$ và $P$ ($1 \le N \le 10^6, 0 \le P \le 10^9$).
  • Dòng 2: Ghi $N$ số nguyên $A_1, A_2, \dots, A_N$ ($0 \le A_i \le 10^9$).
Kết quả ra

In ra một số nguyên duy nhất là độ dài bước nhảy xa nhất tìm được (hoặc $0$ nếu không tồn tại bước nhảy hợp lệ).

Giới hạn
  • Subtask 1 (60% số điểm): $N \le 2000$.
  • Subtask 2 (40% số điểm): $N \le 10^6$.
Ví dụ
Đầu vào 1:
6 3
4 3 7 2 6 4
Đầu ra 1:
3
Đầu vào 2:
7 2
15 2 7 10 1 8 3
Đầu ra 2:
4
Sample Test 1
AC 3 ms 1.2 MB
Sample Test 2
AC 2 ms 1.1 MB
Sample Test 3
AC 3 ms 1.3 MB