{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tIn 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:\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u0026middot; There are three pegs: A, B and C.\u003cbr /\u003e\r\n\t\u0026middot; There are n disks. The number n is constant while working the puzzle.\u003cbr /\u003e\r\n\t\u0026middot; All disks are different in size.\u003cbr /\u003e\r\n\t\u0026middot; The disks are initially stacked on peg A so that they increase in size from the top to the bottom.\u003cbr /\u003e\r\n\t\u0026middot; The goal of the puzzle is to transfer the entire tower from the A peg to the peg C.\u003cbr /\u003e\r\n\t\u0026middot; One disk at a time can be moved from the top of a stack either to an empty peg or to a peg with a larger disk than itself on the top of its stack.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tYour 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.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tTIP: It is well known and rather easy to prove that the minimum number of moves needed to complete the puzzle with n disks is\u0026nbsp; \u003cspan data-scayt_word\u003d\"2n\" data-scaytid\u003d\"2\"\u003e2\u003csup\u003en\u003c/sup\u003e\u003c/span\u003e -1.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t\u003cspan style\u003d\"color: rgb(0, 0, 0);\"\u003eThe input file will consist of a series of lines. \u003cspan style\u003d\"background-color:#ffff00;\"\u003eEach line will contain two integers n, m. n, lying within the range [1,250]\u003c/span\u003e, will denote the number of disks and m, belonging to [0,\u003c/span\u003e\u003cspan data-scayt_word\u003d\"2n\" data-scaytid\u003d\"1\"\u003e\u003cspan style\u003d\"color: rgb(0, 0, 0);\"\u003e2\u003c/span\u003e\u003csup style\u003d\"color: rgb(0, 0, 0);\"\u003en\u003c/sup\u003e\u003c/span\u003e\u003cspan style\u003d\"color: rgb(0, 0, 0);\"\u003e-1], will be the number of the last move, \u003cspan style\u003d\"background-color:#ffff00;\"\u003eyou may assume that m will also be less than 2\u003c/span\u003e\u003c/span\u003e\u003csup style\u003d\"color: rgb(0, 0, 0);\"\u003e\u003cspan style\u003d\"background-color:#ffff00;\"\u003e16\u003c/span\u003e\u003c/sup\u003e\u003cspan style\u003d\"color: rgb(0, 0, 0);\"\u003e, 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.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tThe output will consist again of a series of lines, formatted as show below.\u003cbr /\u003e\r\n\t\u003ci\u003eNOTES\u003c/i\u003e: There are 3 spaces between de \u003d\u0026gt; and the first number printed. \u003cspan style\u003d\"background-color:#ffff00;\"\u003eIf there isn\u0026#39;t any number, there should be no spaces\u003c/span\u003e.\u003cbr /\u003e\r\n\t\u003cspan style\u003d\"background-color:#ffff00;\"\u003eAll the disks in a single peg are printed in a single line.\u003c/span\u003e\u003cbr /\u003e\r\n\t\u003cspan style\u003d\"background-color:#ffff00;\"\u003ePrint a blank line after every problem.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\r\n64 2\r\n8 45\r\n0 0\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\r\nProblem #1\r\n\r\nA\u003d\u0026gt; 64 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\r\nB\u003d\u0026gt;\r\nC\u003d\u0026gt;\r\n\r\nA\u003d\u0026gt; 64 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\r\nB\u003d\u0026gt; 1\r\nC\u003d\u0026gt;\r\n\r\nA\u003d\u0026gt; 64 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\r\nB\u003d\u0026gt; 1\r\nC\u003d\u0026gt; 2\r\n\r\nProblem #2\r\n\r\nA\u003d\u0026gt; 8 7 6 5 4 3 2 1\r\nB\u003d\u0026gt;\r\nC\u003d\u0026gt;\r\n\r\nA\u003d\u0026gt; 8 7 6 5 4 3 2\r\nB\u003d\u0026gt; 1\r\nC\u003d\u0026gt;\r\n\r\nA\u003d\u0026gt; 8 7 6 5 4 3\r\nB\u003d\u0026gt; 1\r\nC\u003d\u0026gt; 2\r\n\r\nA\u003d\u0026gt; 8 7 6 5 4 3\r\nB\u003d\u0026gt;\r\nC\u003d\u0026gt; 2 1\r\n\r\nA\u003d\u0026gt; 8 7 6 5 4\r\nB\u003d\u0026gt; 3\r\nC\u003d\u0026gt; 2 1\r\n\r\nA\u003d\u0026gt; 8 7 6 5 4 1\r\nB\u003d\u0026gt; 3\r\nC\u003d\u0026gt; 2\r\n\r\nA\u003d\u0026gt; 8 7 6 5 4 1\r\nB\u003d\u0026gt; 3 2\r\nC\u003d\u0026gt;\r\n\r\nA\u003d\u0026gt; 8 7 6 5 4\r\nB\u003d\u0026gt; 3 2 1\r\nC\u003d\u0026gt;\r\n\r\nA\u003d\u0026gt; 8 7 6 5\r\nB\u003d\u0026gt; 3 2 1\r\nC\u003d\u0026gt; 4\r\n\r\nA\u003d\u0026gt; 8 7 6 5\r\nB\u003d\u0026gt; 3 2\r\nC\u003d\u0026gt; 4 1\r\n\r\nA\u003d\u0026gt; 8 7 6 5 2\r\nB\u003d\u0026gt; 3\r\nC\u003d\u0026gt; 4 1\r\n\r\nA\u003d\u0026gt; 8 7 6 5 2 1\r\nB\u003d\u0026gt; 3\r\nC\u003d\u0026gt; 4\r\n\r\nA\u003d\u0026gt; 8 7 6 5 2 1\r\nB\u003d\u0026gt;\r\nC\u003d\u0026gt; 4 3\r\n\r\nA\u003d\u0026gt; 8 7 6 5 2\r\nB\u003d\u0026gt; 1\r\nC\u003d\u0026gt; 4 3\r\n\r\nA\u003d\u0026gt; 8 7 6 5\r\nB\u003d\u0026gt; 1\r\nC\u003d\u0026gt; 4 3 2\r\n\r\nA\u003d\u0026gt; 8 7 6 5\r\nB\u003d\u0026gt;\r\nC\u003d\u0026gt; 4 3 2 1\r\n\r\nA\u003d\u0026gt; 8 7 6\r\nB\u003d\u0026gt; 5\r\nC\u003d\u0026gt; 4 3 2 1\r\n\r\nA\u003d\u0026gt; 8 7 6 1\r\nB\u003d\u0026gt; 5\r\nC\u003d\u0026gt; 4 3 2\r\n\r\nA\u003d\u0026gt; 8 7 6 1\r\nB\u003d\u0026gt; 5 2\r\nC\u003d\u0026gt; 4 3\r\n\r\nA\u003d\u0026gt; 8 7 6\r\nB\u003d\u0026gt; 5 2 1\r\nC\u003d\u0026gt; 4 3\r\n\r\nA\u003d\u0026gt; 8 7 6 3\r\nB\u003d\u0026gt; 5 2 1\r\nC\u003d\u0026gt; 4\r\n\r\nA\u003d\u0026gt; 8 7 6 3\r\nB\u003d\u0026gt; 5 2\r\nC\u003d\u0026gt; 4 1\r\n\r\nA\u003d\u0026gt; 8 7 6 3 2\r\nB\u003d\u0026gt; 5\r\nC\u003d\u0026gt; 4 1\r\n\r\nA\u003d\u0026gt; 8 7 6 3 2 1\r\nB\u003d\u0026gt; 5\r\nC\u003d\u0026gt; 4\r\n\r\nA\u003d\u0026gt; 8 7 6 3 2 1\r\nB\u003d\u0026gt; 5 4\r\nC\u003d\u0026gt;\r\n\r\nA\u003d\u0026gt; 8 7 6 3 2\r\nB\u003d\u0026gt; 5 4 1\r\nC\u003d\u0026gt;\r\n\r\nA\u003d\u0026gt; 8 7 6 3\r\nB\u003d\u0026gt; 5 4 1\r\nC\u003d\u0026gt; 2\r\n\r\nA\u003d\u0026gt; 8 7 6 3\r\nB\u003d\u0026gt; 5 4\r\nC\u003d\u0026gt; 2 1\r\n\r\nA\u003d\u0026gt; 8 7 6\r\nB\u003d\u0026gt; 5 4 3\r\nC\u003d\u0026gt; 2 1\r\n\r\nA\u003d\u0026gt; 8 7 6 1\r\nB\u003d\u0026gt; 5 4 3\r\nC\u003d\u0026gt; 2\r\n\r\nA\u003d\u0026gt; 8 7 6 1\r\nB\u003d\u0026gt; 5 4 3 2\r\nC\u003d\u0026gt;\r\n\r\nA\u003d\u0026gt; 8 7 6\r\nB\u003d\u0026gt; 5 4 3 2 1\r\nC\u003d\u0026gt;\r\n\r\nA\u003d\u0026gt; 8 7\r\nB\u003d\u0026gt; 5 4 3 2 1\r\nC\u003d\u0026gt; 6\r\n\r\nA\u003d\u0026gt; 8 7\r\nB\u003d\u0026gt; 5 4 3 2\r\nC\u003d\u0026gt; 6 1\r\n\r\nA\u003d\u0026gt; 8 7 2\r\nB\u003d\u0026gt; 5 4 3\r\nC\u003d\u0026gt; 6 1\r\n\r\nA\u003d\u0026gt; 8 7 2 1\r\nB\u003d\u0026gt; 5 4 3\r\nC\u003d\u0026gt; 6\r\n\r\nA\u003d\u0026gt; 8 7 2 1\r\nB\u003d\u0026gt; 5 4\r\nC\u003d\u0026gt; 6 3\r\n\r\nA\u003d\u0026gt; 8 7 2\r\nB\u003d\u0026gt; 5 4 1\r\nC\u003d\u0026gt; 6 3\r\n\r\nA\u003d\u0026gt; 8 7\r\nB\u003d\u0026gt; 5 4 1\r\nC\u003d\u0026gt; 6 3 2\r\n\r\nA\u003d\u0026gt; 8 7\r\nB\u003d\u0026gt; 5 4\r\nC\u003d\u0026gt; 6 3 2 1\r\n\r\nA\u003d\u0026gt; 8 7 4\r\nB\u003d\u0026gt; 5\r\nC\u003d\u0026gt; 6 3 2 1\r\n\r\nA\u003d\u0026gt; 8 7 4 1\r\nB\u003d\u0026gt; 5\r\nC\u003d\u0026gt; 6 3 2\r\n\r\nA\u003d\u0026gt; 8 7 4 1\r\nB\u003d\u0026gt; 5 2\r\nC\u003d\u0026gt; 6 3\r\n\r\nA\u003d\u0026gt; 8 7 4\r\nB\u003d\u0026gt; 5 2 1\r\nC\u003d\u0026gt; 6 3\r\n\r\nA\u003d\u0026gt; 8 7 4 3\r\nB\u003d\u0026gt; 5 2 1\r\nC\u003d\u0026gt; 6\r\n\r\nA\u003d\u0026gt; 8 7 4 3\r\nB\u003d\u0026gt; 5 2\r\nC\u003d\u0026gt; 6 1\r\n\r\n\r\n\u003c/pre\u003e"}}]}