Elearning CodePath – CTP Online Judge

Farthest Jump

FARTHEST_JUMP

🟢 Hard #General #Binary Search #Two Pointers

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho dãy số nguyên không âm $A = (a_1, a_2, \dots, a_N)$ và một số nguyên không âm $P$.

Một cặp phần tử $(a_i, a_j)$ được gọi là một **bước nhảy** nếu thỏa mãn các điều kiện sau:
1. **Thứ tự chỉ số:** $1 \le i < j \le N$.
2. **Điều kiện giá trị:** $a_j - a_i \ge P$.

Yêu cầu: Tìm **độ dài bước nhảy xa nhất**, được định nghĩa là giá trị **lớn nhất** của $j - i$ trong tất cả các bước nhảy thỏa mãn.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `JUMP.INP`:

* Dòng 1: Gồm hai số nguyên $N$ và $P$.
* Dòng 2: Gồm $N$ số nguyên $a_1, a_2, \dots, a_N$.

Giới hạn:
* $1 \le N \le 10^5$.
* $0 \le P \le 10^9$.
* $0 \le a_i \le 10^9$.

---
### 📤 Định dạng Đầu ra

Ghi vào file `JUMP.OUT` một số nguyên dương duy nhất là độ dài của bước nhảy xa nhất ($j-i$). Nếu không có bước nhảy nào thỏa mãn, ghi $0$.

---
### ✨ Ví dụ

| Input (`JUMP.INP`) | Output (`JUMP.OUT`) |
| :--- | :--- |
| `6 3` <br> `4 3 7 2 6 4` | `3` |

Giải thích: $N=6, P=3$.
* Cặp $(i, j)$ và $a_j - a_i \ge 3$:
    * $(1, 3)$: $a_3 - a_1 = 7 - 4 = 3$. $j-i = 2$.
    * $(2, 3)$: $a_3 - a_2 = 7 - 3 = 4$. $j-i = 1$.
    * $(4, 5)$: $a_5 - a_4 = 6 - 2 = 4$. $j-i = 1$.
    * $(1, 5)$: $a_5 - a_1 = 6 - 4 = 2$ (Không thỏa).
    * $(2, 5)$: $a_5 - a_2 = 6 - 3 = 3$. $j-i = 3$. **(Lớn nhất)**
    * $(4, 6)$: $a_6 - a_4 = 4 - 2 = 2$ (Không thỏa).
Độ dài lớn nhất là $3$.

---
### 🏷 Subtask

Phân chia dựa trên giới hạn $N$ để kiểm tra các thuật toán $O(N^2)$ và $O(N \log N)$ (hoặc $O(N)$).

| Subtask | Ràng buộc | Số điểm ước tính | 
| :--- | :--- | :--- | 
| 1 | $N \le 1000$ | $40\%$ | 
| 2 | $N \le 10^5$ | $60\%$ |

✅ Đã AC: 0 / 1 submissions