Loading...
Loading...
Loading...
At a Diwali fair, Meera plays the three-rod puzzle. Rods are named A, B and C. Rod A holds n disks, numbered 1 (smallest) to n (largest), with the largest at the bottom.
She must move all disks to rod C. She moves one top disk at a time and never puts a larger disk on a smaller one. The shortest way takes 2^n - 1 moves, and there is only one shortest way.
Given n and k, print the k-th move of that shortest way.
d X Y: the k-th move takes disk d from rod X to rod Y.Example 1
Input
3 4
Output
3 A C
The 3 moves before it shift disks 1 and 2 to rod B. Move 4 takes disk 3 from A to C.
Example 2
Input
2 1
Output
1 A B
With 2 disks, the smallest disk first goes to B, out of the way.
Try the problem first. Open one hint at a time.
The shortest way has three parts: move the top n - 1 disks from A to B, move disk n from A to C, then move the n - 1 disks from B to C.
The first part takes 2^(n-1) - 1 moves, so move number 2^(n-1) is the move of disk n.
If k is smaller, the answer is a move inside the first part: n - 1 disks going from A to B with C as the spare rod.
If k is larger, subtract 2^(n-1) and look inside the last part: n - 1 disks going from B to C with A as the spare. Use long and 1L << (n - 1).
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor