You are the operator of a crane. In the reach of the crane there are N locations numbered from 0 to N-1. Initially the location 0 is empty and each of the other locations contains a box with the respective number (i.e. the box in the location i has the number i).
You were assigned a task to rearrange the boxes to form a special top-secret configuration. Because of the secrecy the configuration had to be transferred in a special way that only you can understand.
The secret configuration is characterized by five numbers q, p, m, d and M. To find out the final box locations you should follow this procedure: Consider the boxes in the order of their numbers. (I.e. the box number 1 comes first, the block number 2 second, etc.) The final location for the i-th box will have the number pi=(ci+d*x+y) mod N, where:
Once you find the secret configuration, you are supposed to rearrange the boxes accordingly. Unfortunately there is almost no room to manipulate the boxes. The only operation you are able to do is to lift a box with the crane and drop it on the location that is currently empty. (Note that there will always be exactly one empty location.)
There is one more problem. The whole operation is extremely time-critical and it is imperative that you should achieve the final configuration as soon as possible – i.e. you must reach it using the minimal number of box moves.
1 8 3 5 2 7 4Output:
The recurrence gives the values
The secret configuration is: Box 6 on the location 0, box 5 on the location 1, box 1 on the location 2, location 3 empty, box 4 on the location 4, box 2 on the location 5, box 3 on the location 6 and box 7 on the location 7.
We need 6 moves to reach this configuration.
Contest-related materials: Tom, Martin