In 1883, Edward Lucas invented, or perhaps reinvented, one of the most popular puzzles of all times – the Tower of Hanoi, as he called it – which is still used today in many computer science textbooks to demonstrate how to write a recursive algorithm or program. First of all, we will make a list of the rules of the puzzle: • There are three pegs: A, B and C. • There are n disks. The number n is constant while working the puzzle. • All disks are different in size. • The disks are initially stacked on peg A so that they increase in size from the top to the bottom. • The goal of the puzzle is to transfer the entire tower from the A peg to the peg C. • Onediskatatimecanbemovedfromthetopofastackeithertoanemptypegortoapegwith a larger disk than itself on the top of its stack. Your job will be to write a program which will show a copy of the puzzle on the screen step by step, as you move the disks around. This program has to solve the problem in an efficient way. TIP: It is well known and rather easy to prove that the minimum number of moves needed to complete the puzzle with n disks is 2n − 1. Input The input file will consist of a series of lines. Each line will contain two integers n, m. n, lying within the range [1, 250], will denote the number of disks and m, belonging to [0, 2n − 1], will be the number of the last move, you may assume that m will also be less than 216, and you may also assume that a good algorithm will always have enough time. The file will end at a line formed by two zeros. Output The output will consist again of a series of lines, formatted as show below. NOTES: • There are 3 spaces between de ‘=>’ and the first number printed. If there isn’t any number, there should be no spaces. • All the disks in a single peg are printed in a single line (not as in the Problem #1 below). • Print a blank line after every problem. Sample Input 64 2 8 45 00
2/6 Sample Output Problem #1 A=> 646362616059585756 555453525150494847464544434241 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 B=> C=> A=> 646362616059585756 555453525150494847464544434241 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 B=> 1 C=> A=> 646362616059585756 555453525150494847464544434241 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 B=> 1 C=> 2 Problem #2 A=> 87654321 B=> C=> A=> 8765432 B=> 1 C=> A=> 876543 B=> 1 C=> 2 A=> 876543 B=> C=> 21 A=> 87654 B=> 3 C=> 21 A=> 876541 B=> 3 C=> 2 A=> 876541 B=> 32 C=>
3/6 A=> 87654 B=> 321 C=> A=> 8765 B=> 321 C=> 4 A=> 8765 B=> 32 C=> 41 A=> 87652 B=> 3 C=> 41 A=> 876521 B=> 3 C=> 4 A=> 876521 B=> C=> 43 A=> 87652 B=> 1 C=> 43 A=> 8765 B=> 1 C=> 432 A=> 8765 B=> C=> 4321 A=> 876 B=> 5 C=> 4321 A=> 8761 B=> 5 C=> 432 A=> 8761 B=> 52 C=> 43 A=> 876
4/6 B=> 521 C=> 43 A=> 8763 B=> 521 C=> 4 A=> 8763 B=> 52 C=> 41 A=> 87632 B=> 5 C=> 41 A=> 876321 B=> 5 C=> 4 A=> 876321 B=> 54 C=> A=> 87632 B=> 541 C=> A=> 8763 B=> 541 C=> 2 A=> 8763 B=> 54 C=> 21 A=> 876 B=> 543 C=> 21 A=> 8761 B=> 543 C=> 2 A=> 8761 B=> 5432 C=> A=> 876 B=> 54321 C=>
5/6 A=> 87 B=> 54321 C=> 6 A=> 87 B=> 5432 C=> 61 A=> 872 B=> 543 C=> 61 A=> 8721 B=> 543 C=> 6 A=> 8721 B=> 54 C=> 63 A=> 872 B=> 541 C=> 63 A=> 87 B=> 541 C=> 632 A=> 87 B=> 54 C=> 6321 A=> 874 B=> 5 C=> 6321 A=> 8741 B=> 5 C=> 632 A=> 8741 B=> 52 C=> 63 A=> 874 B=> 521 C=> 63 A=> 8743
6/6 B=> 521 C=> 6 A=> 8743 B=> 52 C=> 61