临近期末,请勿抄袭代码,维护公平!

6194: jump and jump 分享至QQ空间

Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte
Total Submit: 518            Accepted:97

Description

寒假在家里无聊极了,小w看到地上的瓷砖,想出了一个游戏。这个游戏是这样子的,一共有n个格子,刚开始在起点的时候可以跳到第1个到第k个格子中的一个上面,之后在每个格子上只能向前跳相对应的长度。请问至少需要多少步可以恰好跳到最后一个格子呢?


Input

第一行输入两个整数n和k(1<=n<=100000,1<=k<=n)。

第二行输入n个整数,第i个整数代表在第i个格子上能跳跃的长度(0<=a[i]<=100000)。

Output

输出能跳到第n个格子的最少步数。如果无法到达,输出-1。

Sample Input

Sample Output

Hint

在起点跳到第1个位置,1->5->7

在起点跳到第2个位置,2->4->5->7

在起点跳到第3个位置:3->8

Source

2020年常熟理工学院第一届线上ACM选拔赛

Uploader

z469701917


[Submit] [Status]

|Back |   | Top|
Copyright @ 2008-2022(浙ICP备2022001332号), TZOJ. All Rights Reserved.