Problem C: Buying Gas
Gasoline is expensive these days. Many people go out of their way to
find the cheapest gas. You could write a computer program to help
with this. But on the other hand, searching around too much can
waste a lot of time. It could even happen that the driver searches
so long that he runs out of gas, which is a major nuisance.
Deciding where to buy gas is even more important on a long trip.
Such a trip already takes a long time, so you don't want to waste
any more time than you have to. And the consequences of running
out are all the more bothersome when far away from home.
Your task here is to write a program that finds the optimal places
where to buy gas on a long trip. Of course, the answer must ensure
that the car never runs out of gas. Furthermore, it must minimize
the number of times that the car stops to fill up.
Input Specification
The first line of input contains three integers 0 < n <=
100, 0 <= m <= 100000, 0 <= d <=
100000, the capacity of the gas tank in litres, the number of
gas stations along the route, and the total length of the trip in
kilometres. The following m lines each contain two integers,
the distance in kilometres from the starting point of the trip to the
gas station, and the price of gas at the gas station in tenths of a cent
per litre. The car begins the trip with a full tank of gas, and uses 0.1
litres of gas for each kilometre travelled.
Sample Input
50 2 1000
500 1293
750 1337
Output Specification
Find the optimal set of gas stations at which to stop to get gas.
Output a single integer, the number of gas stations in this set.
If it is not possible to make the trip without running out of
gas, output the integer -1.
Output for Sample Input
1
Ondřej Lhoták
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.