No.1868 Teleporting Cyanmond
タグ : / 解いたユーザー数 160
作問者 :
shiomusubi496
/ テスター :
ぷら
kaichou243
Problem Statement
There are $N$ towns $1, 2, \ldots, N$ lined up on a straight line in this order. Cyanmond is currently in town $1$ and wants to travel to town $N$.
Each town other than town $N$ has a teleporter, and from town $i$ one can teleport to any of the towns $i+1, i+2, \ldots, R_i$.
Cyanmond wants to get to town $N$ as quickly as possible. Tell Cyanmond the minimum number of teleports needed to reach town $N$.
(Original idea: Cyanmond)
Input
$N$
$R_1$ $R_2$ $\cdots$ $R_{N-1}$
- $2 \leq N \leq 10^5$
- $i < R_i \leq N$ $(1 \leq i \leq N - 1)$
- All inputs are integers.
Output
Output the minimum number of teleports needed to reach town $N$.
Sample
Sample 1
Input
5 2 4 4 5
Output
3
For example, traveling through towns in the order $1 \to 2 \to 4 \to 5$ is optimal.
Sample 2
Input
8 8 8 8 8 8 8 8
Output
1
It is possible to move directly from town $1$ to town $8$.
Sample 3
Input
20 4 7 7 6 10 9 8 9 13 15 13 16 17 15 18 18 20 20 20
Output
6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。