3021: [SDOI2020小学组] 勇敢的津津(jump)
Memory Limit:256 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
津津是个勇敢的孩子,总是做一些挑战自己的事情。
一天津津来到一条宽为 L 米的小河边,河道的一边到另一边需要途径 N 块较大的石墩,每块石墩到这一边岸边之间距离 x~i~ 米(石墩不占距离,只考虑石墩的中间点到这一边岸边之间距离)。
津津想踩着这些石墩从小河的这一边跳到另一边(不落入水中),一次可以跳过几块石墩。
已知津津每次最多跳 M 米的距离,那么津津最少跳几次就能从这一边跳到另一边?
Input
第一行包含三个整数 L,N, M,分别小河的宽度、石墩数和津津跳的最远距离。
接下来 N 行,每行一个整数,第 i 行的整数 d~i~( 0
Output
一个整数,即最少的跳跃次数。
Sample Input Copy
10 4 2
2
4
6
8
Sample Output Copy
5
HINT
**【样例解释】**
样例一:津津可以从岸边跳到距离为 2 石墩上,然后跳到距离为 4 的 石墩上,再跳到距离为 6 的石墩上,再跳到距离为 8 的石墩上,最后跳的对岸。总共 5 跳跃。
样例二:津津可以从岸边跳到距离为 2 石墩上,然后跳到距离为 11 的
石墩上,再跳到距离为 21 的石墩上,最后跳的对岸。总共 4 跳跃。
**【数据范围】**
对于 30% 的数据,1≤N≤10。
对于 50% 的数据,1≤N≤100。
对于 100%的数据,1≤N≤500,1≤M,L≤1,000,000。