Số bước nhảy ít nhất

General
Points
38
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề 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$.
Draft saved