Problem G
Truckin’
Input:
Standard
Input
Output: Standard Output
Time Limit: 8 Seconds
A truck driver has a regular route down a long
stretch of highway. There are intersections
with traffic lights at sections along this highway. He would like to plan his trip so that he does not spend any
time waiting at red lights. He knows
the period of each traffic light, so this is simple enough. However, fuel is costly, so he also
wants to conserve fuel as much as possible. Help him determine the minimum
amount of fuel required for the journey.
When driving at a
constant speed of v meters per second, the rate of fuel consumption is assumed
to be v + 1/v - 0.1 milliliters per second.
Traffic lights
stay red for a certain length of time, then turn green for a certain length of
time, and repeat indefinitely.
When the driver starts out, all lights are just starting their red
cycle.
Every case begins with a line containing
integers D, the distance to travel in meters, and L, the number
of traffic lights along the route.
The next L lines will each contain three positive integers d,
r, and g. d is the distance along the route of this light,
and r and g are the length in seconds of the red and green
cycles, respectively.
No route will
be longer than 10000 meters, and there will never be more than 50
traffic lights along a route.
Complete light cycles always take between 30 and 90 seconds. Traffic lights will be specified in
order of distance along the route (and will not overlap each other or the
beginning and end of the route).
Input will be terminated with a line containing two 0s. There will be at most 15 test cases.
For each case, output one line consisting of the minimum fuel required (in milliliters) to make the journey as described, accurate to two decimal places.
|
1000
3 250
20 20 500
40 40 750
19 19 0 0 |
998.03
|
Problem setter: Derek
Kisman, Member of Elite Problemsetters' Panel