ゴールまでの最短距離 VB(Beta)編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
整数 N と N 個の要素からなる配列 A = [ A_0, A_1, ..., A_{N - 1} ] が与えられます。
あなたは 座標 0 にいる状態から移動を繰り返して 座標 N - 1 にたどり着くことを目指します。
座標 i には A_i が書かれており、座標 pos(0 ≦ pos < N - 1) にいるとき、1 回の移動で以下のどちらかを行うことができます。
・座標 {pos + 1} へ移動する
・A_pos = A_{new_pos} である座標 new_pos(pos < new_pos) へ移動する
座標 A_N にたどり着くために必要な最小の移動回数を出力してください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N
A_0
A_1
.
.
.
A_{N - 1}
・1 行目には 整数 N が与えられます。
・続く N 行には配列 A の要素が 1 行に 1 つ与えられます。
・入力は合計で N + 1 行からなり、入力値最終行の末尾に改行が１つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
A_N にたどり着くために必要な最小の移動回数を 1 行に出力してください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・2 ≦ N ≦ 100000
・1 ≦ A_i ≦ 100000
・N, A_i は整数
- 入力例1
-
10
1
4
2
4
3
3
4
2
5
5
- 出力例1
-
5
- 入力例2
-
20
4
2
5
1
4
3
8
1
6
2
3
5
1
1
1
3
4
10
8
2
- 出力例2
-
2
