Determine when the world will end
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:
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.
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:
An example input file would be
column 111111111122222222223 123456789012345678901234567890 line 1:1721 10 19 23[EOL] 2:2001 11 17 59[EOL] :[EOF]
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.
column 111111111122222222223 123456789012345678901234567890 line 1:Program 0 by team 0[EOL] 2:840297140021.6[EOL] 3:2192079493218.6[EOL] 4:End of program 0 by team 0[EOL] :[EOF]