Elearning CodePath – CTP Online Judge

NewYearTransportation

GEN038

🟢 Medium #BFS/DFS

---

### 📝 Bài toán
Năm mới sắp đến ở Line World! Trong thế giới này có n ô, được đánh số từ 1 đến n, tạo thành một bảng 1 × n. Mỗi ô có người sinh sống. Tuy nhiên, việc di chuyển giữa các ô rất khó khăn.

Để mọi người có thể gặp nhau, người dùng tncks0121 đã tạo ra một hệ thống dịch chuyển giữa các ô.

Trước hết, anh ta nghĩ ra n − 1 số nguyên dương a₁, a₂, ..., aₙ₋₁.

Với mỗi i (1 ≤ i ≤ n − 1), ta có:
* 1 ≤ aᵢ ≤ n − i

Sau đó, anh ta tạo ra n − 1 cổng dịch chuyển, được đánh số từ 1 đến n − 1.
* Cổng thứ i nối ô i với ô (i + aᵢ).
* Ta chỉ có thể đi từ ô i đến ô (i + aᵢ) bằng cổng này.
* Không thể đi ngược lại từ ô (i + aᵢ) về ô i.

Do điều kiện 1 ≤ aᵢ ≤ n − i, nên chắc chắn không thể đi ra ngoài Line World.

**Yêu cầu:**
Hiện tại, tôi đang đứng ở ô số 1, và tôi muốn đi đến ô số t. Hãy xác định xem có thể đi đến ô t hay không, chỉ bằng cách sử dụng hệ thống dịch chuyển đã cho.

---

### 📥 Định dạng Đầu vào
* Dòng 1: Hai số nguyên n và t (3 ≤ n ≤ 3 × 10⁴, 2 ≤ t ≤ n)
* Dòng 2: n − 1 số nguyên a₁, a₂, ..., aₙ₋₁ (1 ≤ aᵢ ≤ n − i)

**Giới hạn:**
* 3 ≤ n ≤ 3 × 10⁴
* 2 ≤ t ≤ n
* 1 ≤ aᵢ ≤ n − i

Đảm bảo rằng không thể rời khỏi Line World bằng các cổng đã cho.

---

### 📤 Định dạng Đầu ra
* In ra "YES" nếu có thể đi từ ô 1 đến ô t.
* Ngược lại, in ra "NO".

---

### ✨ Ví dụ

**Ví dụ 1:**
| Input | Output |
| :---: | :---: |
| `8 4`<br>`1 2 1 2 1 2 1` | `YES` |

**Giải thích Ví dụ 1:**
Các ô có thể đi qua là: 1 → 2 → 4, nên có thể đến ô 4.

---

**Ví dụ 2:**
| Input | Output |
| :---: | :---: |
| `8 5`<br>`1 2 1 2 1 1 1` | `NO` |

**Giải thích Ví dụ 2:**
Các ô có thể đi qua là: 1 → 2 → 4 → 6 → 7 → 8, không thể đến ô 5.

---

### 🏷 Ràng buộc
| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- | 
| 1 | n ≤ 100 | 40% |
| 2 | n ≤ 3 × 10⁴ | 60% |

✅ Đã AC: 8 / 12 submissions