0458 - すごろく

時間制限 1 秒 / メモリ制限 64 MB / 得点 10 / Writer root / x 2 / 統計 /

    タグ:

TLE
1sec
MLE
64MB
得点
10

お詫び:OutputFileに誤りがあったため訂正とリジャッジを行いました.
2016/07/12 21:16

OutputFileの強化を行い,リジャッジを行いました.
誤りのお詫びとして下記にヒントを書き加えました.
2016/07/12 21:25

問題

1~Nのマスのすごろくがある.
このすごろくは環になっており,Nの次は1に戻る.
各マスには-10000~10000までの数piが振られている.

1~6までの目を持つサイコロを振った後,出た目の数だけプラス方向にコマをすすめる.
そして止まった目に書いてある数piだけコマを更に移動させる.
piが正の数ならプラス方向に,負の数ならマイナス方向に進める(0なら移動させない).

1のマスからスタートした場合ちょうどNマス目に辿り着くには最低何回サイコロを振らなければならないか求めよ.
辿り着くことが出来ない場合は-1を出力せよ.

入力


N
p1
.
.
.
pN         
  

1行目に整数 N が与えられる.

その後N行にわたり整数 pi が与えられる。

出力

1のマスからスタートした場合ちょうどNマス目に辿り着くには最低何回サイコロを振らなければならないか出力せよ.
辿り着くことが出来ない場合は-1を出力せよ.

制約

全ての入出力ケースは整数であり以下を満たす。

  • 2 ≦ N ≦ 1000000
  • -10000 ≦ pi ≦ 10000

入出力例

入力例1

10
1
2
3
4
5
6
7
8
9
-5

出力例1

1

解説

4の目のサイコロを振るとそこから更に5マス進むことが出来る為,無事Nのマスに辿り着くことが出来る.


入力例2

10
-1
-2
-3
-4
-5
-6
-7
-8
-9
-10

出力例2

1

解説

1の目のサイコロを振るとそこから更に-2マス進むことが出来る為,無事Nのマスに辿り着くことが出来る.


入力例3

6
0
5
4
3
2
1

出力例3

-1

解説

必ず1のマスに戻って来てしまうため,Nのマスに辿り着くことが出来ない.
よって-1を出力せよ.


~~~~~誤りのお詫びとして大ヒント~~~~~
自然数a, bが与えられた時 -a%b をするとC言語では剰余の答えが -c になってしまう.

そこでaが負数を含む可能性があるときは ((a%b)+b)%b とするとaが正数,負数関係なく剰余の答えが自然数c'になるのではっぴーになれるかも.

なぜこの式が良いのかは各自考察ください.