Many thanks to Clive Fraser for this task!
The abbot of the monastery at Hanoi is getting worried about his monks. They are becoming fat and are suffering from stress. After careful consideration the abbot decided that the Towers of Hanoi were the main cause of the problem. The monks spent too much of their time sitting alongside the three towers of discs and agonising over the next move, because they were so worried about the possibility of making a mistake. The abbot decided that the monks needed more exercise and a stress free environment which would allow them time to practise their meditation. With these aims in mind, he decided to replace the Towers of Hanoi with something more suitable.
After much thought the abbot came up with a plan. The three towers would be replaced by a much larger number of towers. The towers would still consist of a tall vertical peg fixed into the ground. The abbot decided that he would also retain the doughnut shaped discs which fit over the central peg. However, all of the discs would now be identical (unlike the previous discs which were all different sizes). The towers were to be arranged in a long straight line. Initially the towers would be set up so that there is a random number of discs on each peg. The abbot wanted the rules for moving a disc to be so simple that there would be no significant thought required in finding the correct next move. This would mean that the monks' meditation would not be impaired. The exercise requirement could also be met by requiring a monk to walk a significant distance in order to make a move.
One end of the line of towers is designated as a starting point. To make a move, a monk must begin at this position and walk along the line of towers until he locates the first tower where the number of discs is smaller than the number of discs on the previous tower. The monk then completes the move by transferring a single disc from the previous tower to the current tower, before returning to the starting point. All of the monks are required to make a minimum of one move per day.
After implementing the new towers, the abbot was delighted to see the effect on his monks. The extra walking soon improved their overall health and fitness. The simplicity of the disc moves was a considerable relief to those monks who had suffered considerable anxiety in trying to decide which of the possible next moves was the correct one. In fact the monks were so pleased with the new arrangement that many of them opted to make more than one move per day.
Clearly, after a finite (but very large) number of moves there will no longer be any valid move remaining on the line of towers. There will be
no tower where the number of discs is smaller than the number on the previous tower. The abbot is aware of this but is not concerned. If such a
situation arises he will simply re-randomise the numbers of discs on the towers so that the process can continue. This is a much better outcome
than the one corresponding to the final move of the 3 tower version; where the world comes to an end!
In this problem you will be given the initial number of discs on each of the towers and are to determine the number of moves that can be made
before we reach the point when there is no longer any valid move. Consider the following simple example which uses only 5 towers (N = 5).
The starting point is on the left and the numbers show the number of discs on each tower, both at the start and after each move.
Start: 8 6 7 5 9
Move 1: 7 7 7 5 9
Move 2: 7 7 6 6 9
Move 3: 7 6 7 6 9
Move 4: 6 7 7 6 9
Move 5: 6 7 6 7 9
Move 6: 6 6 7 7 9
Starting from the left (at the start) we see that tower 2 is the first tower with fewer discs than the previous tower (6 < 8). Thus we
transfer 1 disc from tower 1 to tower 2. Both of these towers now have 7 discs. Note that this is the only allowed first move. Although
the 4th tower has fewer discs than the third tower we are not allowed to make this move because it is not the first such occurrence after the
starting position. At any point in the process there is only one allowed move, until we reach the stage when there is no valid move available.
In the example above this occurs after 6 moves.
For the actual problem we will use the Linear Congruential Generator to generate the numbers
of discs on each of the towers. This has been used before in Code Abbey problems. A random value X(n) is generated using the formula:
X(n) = (A * X(n-1) + C) % M
In this problem we will use the values A = 445, C = 700001 and M = 2097169. Note that % M means the remainder after dividing by the
modulus value of M. The value X(n-1) is the previous random value to be generated by this expression. In order to generate the first random
value X(1) we need to be given a value for X(0) which is called the seed for the generator. This value will be supplied as part of the data
for the problem.
The example below is made deliberately small (N = 10) so that you can use it to test your ideas. For this example, the random seed X(0) is
taken to be 0 (it will not be 0 in the actual problem). We need 10 numbers for the numbers of discs on the 10 towers. The first 10
values generated for X(n) are
700001 1819434 840897 1603084 1034921 1959835 404272 244507 452828 880237
With these numbers of discs on the towers, the number of moves needed to complete the puzzle is 8268807. The number of towers in the actual
problem will be very much larger.
Input/Output description:
The first and only line of the input data will contain two space separated integers, the random seed X(0) and the problem size N
(the number of towers).
Your answer is the number of moves needed to complete the puzzle (when there is no valid move remaining).
Example:
input:
0 10
answer:
8268807