Programming Problem #18
"The Thief of Baghdad"
The 150-floor Baghdad Office Building is on fire! On each floor of this high-rise
building is a sack of gold coins. As an enterprising thief, you want to know
the maximum number of coins you can safely steal, subject to the following
conditions:
- You must use the elevator, which moves at a speed of 10 floors per minute.
- You are in the elevator on the first floor when the fire starts.
- The elevator can't move through or stop at a floor that is on fire.
You also can't stop at a floor if the fire will arrive while you are there.
- It takes 10 seconds to get the sack of coins from a floor, regardless of
how many coins the sack contains. Once you have retrieved the coins from a
floor, you are no longer considered to be on that floor.
- The fire spreads down at a rate of one floor per minute. (Of course
the fire also spreads up, but you must always remain below the fire.)
The input contains one or more building descriptions. Each building
description begins with a line containing an integer 0 <= N <= 150,
indicating the floor that the fire starts on. If N is zero it signals the
end of the input. Otherwise, one or more lines will follow that
contain two integers F and C, separated by a space. The pair (F,C)
indicates that floor F has a sack of C coins. Floors are numbered consecutively
starting at 1, and a floor will have at most 100 coins. The pairs may be listed in
any order, and there will be at most one pair for each floor. Floors not
listed have no coins. The pair (0,0) signals the end of a building
description.
For each building description, simply output a line containing the maximum
number of coins that can safely be retrieved before the building is consumed
by the fire.
Input must be read from the file "prob18.in",
and output must be written to the file "prob18.out".
All output to the screen will be ignored.
Example Input
<BOF>
10
34 50
17 100
50 6
0 0
75
35 11
70 100
104 66
17 5
2 84
0 0
0
<EOF>
Example Output
0
100
A version of this problem originally appeared in the 1989 ACM finals.
Dr. Eric Shade