Too Lazy To Move

Time Limit : 10000/5000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 0 Accepted Submission(s) : 0

Problem Description

As we all know, Hanoi Tower can be solved in 2^n-1 steps if there are n disks.
We might adhere to such rules:
1) When the step number is odd, move the smallest disk to the next pillar (in
the order A->B->C->A��). 
 
2) When the step number is even, move one disk between the pillar without the
smallest disk.
Here is an example: 
 
Step 0 (Initial Step) 
A: 3 2 1 
B: 
C: 
 
Step 1 
A: 3 2 
B: 1 
C: 
 
Step 2 
A: 3 
B: 1 
C: 2 
 
Step 3 
A: 3 
B: 
C: 2 1 
 
Step 4 
A: 
B: 3 
C: 2 1 
 
Step 5 
A: 1 
B: 3 
C: 2 
 
Step 6 
A: 1 
B: 3 2 
C: 
 
Step 7 
A: 
B: 3 2 1 
C: 
 
End. 
 
Now it is your task to find out the m-th configuration for a n-disk Hanoi Tower
with the rules defined above.
 
Input
One test on each line, with two integers n (1 <= n <= 63) and m (0 <=
m <= 2^n-1). Input is terminated with end of file.
 
Output
Print a configuration in three lines. Conform to the format in the sample.
There should be one space after each colon. Each test is followed by a blank
line.
 
Sample Input
3 0 
3 1 
3 2 
3 7 
63 9223372036854775807
 
Sample Output
A: 3 2 1 
B: 
C: 
A: 3 2 
B: 1 
C: 
A: 3 
B: 1 
C: 2
A: 
B: 3 2 1 
C: 
A: 
B: 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39
38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3 2 1 
C:

Source

ZOJ Monthly, March 2003

Statistic | Submit | Back