2.新飞行棋
题目描述
期末考试终于结束了。Andy同学感觉松了一口气,他决定重温小时候的快乐时光--下飞行棋。
但是他弄丢了传统飞行棋需要的骰子,因此他发明了一种新型的飞行棋游戏,规则如下:棋盘上有n个格子,由近到远分别编号为1到n。对于1<=i<=n,第i个格子上写着一个正整数Ni。当玩家处于第a个格子时,他可以选择往后走Na步,或者往前倒退Na步。当然如果Na+a>n,那么他就只能选择后退;同理如果a-Na<1,那么他就只能选择前进。保证不会出现既不能前进又不能后退的格子。
Andy学完编程后对一个问题很感兴趣:从编号s出发,至少需要经过几把,可以到达t点?(例如在a点选择往前走Na步,称之为一把)。
输入格式
从文件fly.in中读取数据。
第一行三个整数,分别为n,s,t意义如题面所述。
第二行n个正整数,第i个数为Ni。
输出格式
输出到文件fly.out中去。
一个数,为最少经过的把数。如果s无法到达t,输出-1。
样例输入
6 6 4
1 2 2 3 1 2
样例输出
1
数据规模与约定
对于前10%的数据,s=t;
对于前40%的数据,n<=200;
对于另外10%的数据,s无法到达t;
对于100%的数据,n<=200000;
信息
- ID
- 1009
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 69
- 已通过
- 3
- 通过率
- 4%
- 上传者