Problem B
Flight Planner
Input: standard input
Output: standard
output
Time Limit: 1 second
Memory Limit: 32 MB
Calculating the minimal cost for a flight involves calculating an optimal flight-altitude
depending on wind-strengths changing with different altitudes. It's not enough
just to ask for the route with optimal wind-strength, because due to the mass
of a plane you need a certain amount of fuel to rise. Moreover due to safety
regulations it's forbidden to fly above a certain altitude and you can't fly
under zero-level.
In order to simplify the problem for now, we assume that for each 100 miles
of flight you have only three possiblities: to climb one mile, to hold your
altitude or to sink one mile.
Climb flight requires 60 units of fuel, holding your altitude requires 30
units and sinking requires 20 units.
In the case of headwind you need more fuel while you can save fuel flying
with tailwind. Windstrength w will satisfy the condition -10 <= w <= 10,
where negative windstrength is meant to be headwind and positive windstrength
is tailwind.
For one unit of tailwind you can save one unit of fuel each 100 miles; each
unit of headwind will cost an extra unit of fuel.
For example to climb under conditions of windstrength w = -5, you need 65
units of fuel for this 100 miles.
Given the windstrengths on different altitudes for a way from here to X,
calculate the minimal amount of fuel you need to fly to X.
The first line of the input file contains the number N of test cases in the
file. The first line of each test case contains a single integer X, the
distance to fly, with 1 <= X <= 100000 miles and X is a multiple of 100.
Notice that it's not allowed to fly higher than 9 miles over zero and that you
have to decide whether to climb, hold your altitude or to sink only for every
100 miles.
For every mile of allowed altitude (starting at altitude 9 down to altitude 0)
there follow X/100 windstrengths, starting with the windstrength at your
current position up to the windstrength at position X-100 in steps of 100
miles. Test cases are separated by one or more blank lines.
For each test case output the minimal amount of fuel used flying from your
current position (at altitude 0) to X (also at altitude 0), followed by a blank
line.
2
400
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 9 9 1
1 -9 -9 1
1000
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
7 7 7 7 7 7 7 7 7 7
-5 -5 -5 -5 -5 -5 -5 -5 -5 -5
-7 -3 -7 -7 -7 -7 -7 -7 -7 -7
-9 -9 -9 -9 -9 -9 -9 -9 -9 -9
120
354
Frank Hutter