TOWERS OF HANOI
Determine when the world will end
The Towers of Hanoi is a classic recursion problem:
N disks, of size N through 1, are stacked in order on the left post
of three posts, so the largest disk is on the bottom.
The game is to move the stack of disks from the first post to the third
post under the following constraints:
-
You may only move one disk at a time.
-
The disks on each post remain sorted from large (bottom) to small (top).
This can be accomplished recursively: to move K disks from post A to post
C, first move K-1 disks to the remaining post, B, then move the one remaining
disk from post A to post C. Moving the K-1 disks from post B to C is a
reduced version of the original problem where the posts have been relabeled.
Legend has it that the Order of the Andes-Chilean Monks, also known
as the Order of the ACM, have started the work of moving a 60-disk tower.
When they finish, the world will end. Using the above recursive algorithm,
this will take 1,152,921,504,606,846,975 moves.
You are to determine, to within a year, when the world will end.
INPUT: hanoi.in
OUTPUT: hanoi.out
The input file will contain a sequence of starting times and rates
in the format:
Here YYYY MM DD is the year, month, and day, using the Gregorian
calendar, when the tower game began. TMOVE is the number of seconds
it takes to move one disk, and is an integer value in the range 0 <
TMOVE
< 60. Since the Gregorian calendar system would introduce a significant
phase error over this time span, use the following convention:
-
Use Gregorian calendar conventions to convert the starting date to decimal
year.
-
Use the estimate that there are 365.242199 days in a year to determine
the ending date of the world.
-
Report your result using decimal year notation with one digit of precision
after the decimal point.
An example input file would be
1721 10 19 23
2002
11 24 23
The output should be in decimal year format, with one digit of precision
after the the decimal point. The answer must be correct to with a year.
840297140021.6
840297140302.7