Petrol stations P40710


Statement
 

pdf   zip

thehtml

A car driver needs to plan a journey following a highway. With the tank full he can drive for at most x kms. Knowing the location of the n petrol stations on the road, which is the minimum number of refill stops necessary to travel for at least D kms? Assume that, initially, the tank of the car is full of gasoline.

Input

Input is all natural numbers, and consists of several cases. Every case begins with x and ‍D, followed by n, followed by the distances in kms from the departure point to each petrol station. Assume x > 0, D > 0, n ≤ 105, and that all the given distances are different and between 1 and D−1. For all the given cases, it is always possible to reach the km D.

Output

For every case, print the minimum number of stops to travel for at least D kms.

Public test cases

  • Input

    2 5
3   1 3 4
3 10
4   1 8 6 4
15 10
6   5 2 9 4 1 3

    Output

    2
4
0
    • Information
    Author
    Amalia Duch
    Language
    English
    Official solutions
    C++ Python Python
    User solutions
    C++ Python