Số bước nhảy ít nhất
Points
38
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề bài
Cho dãy $A$ gồm $N$ số nguyên không âm, đánh số từ $1$ đến $N$. Bạn bắt đầu tại vị trí $1$. Từ vị trí $i$, bạn có thể nhảy tới bất kỳ vị trí $j$ nào thỏa mãn $i < j \le \min(N, i + A_i)$. Hãy tìm số bước nhảy ít nhất để đi tới vị trí $N$. Nếu không thể đi tới $N$, in ra -1.
Dữ liệu vào
Dòng đầu chứa số nguyên $N$. Dòng thứ hai chứa $N$ số nguyên không âm $A_1, A_2, \dots, A_N$.
Dữ liệu ra
In ra số bước nhảy ít nhất, hoặc -1 nếu không thể tới vị trí $N$.
Ví dụ
| Input | Output |
|---|---|
| 5 2 3 1 1 4 |
2 |
| 5 3 2 1 0 4 |
-1 |
Giới hạn
- $1 \le N \le 10^5$.
- $0 \le A_i \le 10^5$.
Community Discussion