Problem D
Driver's Dilemma
A car driver visiting Canada from the US travels on a road through isolated New Brunswick territory (no gas stations, houses, or cell phone coverage). Ominous road signs warn about collision risks from deer and moose after dark. Suddenly the driver glances at his fuel gauge with shock: there is exactly half a tank left. He stops and sees that his fuel tank is leaking, which accounts for some of the fuel gauge drop since the last fill up.
The driver cannot repair the leak. Using a container of known volume and his wristwatch, he measures the rate of fuel loss at $X$ gallons per hour. He empties the container back into the tank. He must quickly figure out what to do.
The driver checks the owner’s manual for his rented compact car and finds that the fuel tank capacity is $C$ gallons. He also notices a table resembling (but not necessarily identical to) the one in the figure below, showing declining fuel efficiency in miles per gallon (MPG) as driving speed in miles per hour (MPH) increases. He must trade one against the other in an attempt to reach the nearest gas station $M$ miles away before nightfall.
Since the driver assumes that people who write manuals must be experts, and since he has an aversion to interpolation (and also to extrapolation), he decides that he will drive at exactly one of the $6$ speeds listed in the table. That way, the distance he can travel before running out of gas will be $100\% $ predictable.
Can the driver reach the gas station before running out of fuel? If so, at what maximum speed can he drive?
|
Speed (MPH) |
Fuel Efficiency (MPG) |
|
$55$ |
$22.0$ |
|
$60$ |
$21.3$ |
|
$65$ |
$20.2$ |
|
$70$ |
$18.3$ |
|
$75$ |
$16.9$ |
|
$80$ |
$15.8$ |
Input
Input consists of a single test case occupying $7$ lines. The first line contains $3$ space-separated real numbers: the capacity $C$ of the tank in gallons, the rate of the fuel leak $X$ in gallons per hour, and the distance $M$ in miles to the next gas station, with $0 < C, X \leq 100$ and $0 < M \leq 500$. Each of the remaining $6$ lines contains an integer followed by a real number (separated by a space). The $6$ integers at the beginning of these $6$ lines are exactly the values in the left column of the table above, in the same order. The corresponding $6$ real numbers are in strictly decreasing order, and each such number $f$ satisfies $0 < f \leq 50$. Every real value in the input has at most $2$ digits after the (optional) decimal point.
Output
If it is possible for the driver to reach the nearest gas station without running out of gas, output “YES” followed by the highest speed at which the driver can drive (separated by a space). This highest speed must be one of the integers $55, 60, 65, 70, 75, 80$. If it is impossible for the driver to reach the nearest gas station before running out of gas, output “NO”. To avoid rounding errors, the following two things are guaranteed: ($1$) If the driver can reach the gas station, there will be at least $10^{-6}$ gallons remaining in the tank when he arrives. ($2$) If the driver cannot reach the gas station, then he would have required at least $10^{-6}$ more gallons of gas in order to be able to do so.
| Sample Input 1 | Sample Output 1 |
|---|---|
18 0.5 160 55 22.0 60 21.3 65 20.2 70 18.3 75 16.9 80 15.8 |
YES 60 |
| Sample Input 2 | Sample Output 2 |
|---|---|
16 0.07 160 55 20.49 60 18.40 65 17.78 70 17.10 75 16.38 80 15.60 |
NO |
