[r] En 1883, Edouard Lucas inventó, o tal vez reinventó, uno de los rompecabezas más populares de todos los tiempos — la Torre de Hanoi, como él le llamó — y que aún se usa hoy día como prototipo de algoritmo recursivo. De hecho, muchos libros de texto para estudiantes de ciencias de la computación, lo ponen como ejemplo para implementar en forma de programa la idea de recursividad. Estas son las reglas del juego:
Aunque, naturalmente, la mejor forma de iniciarse en los secretos de este rompecabezas es intentar resolverlo sobre uno de los muchos y variados modelos reales que se encuentran en las tiendas de regalos, si esto no es posible, una buena forma de captar la esencia del juego es escribir un programa que nos muestre en la pantalla un modelo del mismo y nos permita simular el movimiento de los discos. Pero no es esto lo que vamos a proponer en esta tarea. El siguiente paso sería escribir un programa que nos resuelva el rompecabezas de la manera más eficiente posible. Tampoco es éste el objetivo de esta tarea. El objetivo que se persigue es la implementación de un algoritmo eficiente para saber el estado de cada una de las tres torres de discos en cada etapa del proceso de solución del juego. Para facilitar la tarea, no pedimos el detalle de los discos que hay insertados en cada poste, sino únicamente cuántos hay después de un determinado movimiento, cuando se resulve el rompecabezas siguiendo un algoritmo concreto, que pasamos a describir.
Se conoce perfectamente, y es muy fácil de demostrar, que el número mínimo de movimientos de discos que hay que hacer para completar el cambio de la torre original a otro poste distinto es 2n − 1, siendo n el número de discos. Un algoritmo muy sencillo, pero que nos permite resolver el rompecabezas en esta cantidad óptima de movimientos es el siguiente: para los movimientos impares, se coge el disco más pequeño de todos (digamos el número 1) del poste en el que está insertado y se le coloca en el siguiente dentro de la sucesión circular ABCABC …; para los movimientos pares, se hace el único movimiento posible que no implique a dicho disco número 1.
Entrada
El fichero de entrada consiste en una serie de líneas. Cada una de ellas contiene dos números enteros n, m: n es el número de discos y m, que estará en el intervalo [0, 2n − 1], será el número del último movimiento realizado. El fichero termina con una línea que contiene dos ceros y no se debe procesar.
Salida
La salida consiste también en una serie de líneas, una por cada una del fichero de entrada (excepto la última). Cada una de ellas estará formada por tres números enteros, que representan el número de discos en cada uno de los postes A, B and C respectivamente, después del movimiento m, y teniendo en cuenta que dichos movimientos se han hecho de acuerdo con el algoritmo descrito.
Puntuación
100 casos de pruebas con n≤ 16.
100 casos de pruebas con n≤ 50. El número m puede no caber en un entero de 32 bits, por lo que será necesario utilizar enteros de 64 bits, como el tipo long long de C o C++.
100 casos de pruebas con n≤ 100.
Input
1 0 1 1 2 0 2 1 2 2 3 0 3 1 3 2 3 3 3 4 3 5 3 6 3 7 0 0
Output
1 0 0 0 1 0 2 0 0 1 1 0 0 1 1 3 0 0 2 1 0 1 1 1 1 0 2 0 1 2 1 1 1 1 2 0 0 3 0
Input
3 5 8 45 39 437370956880 0 0
Output
1 1 1 4 2 2 17 12 10
Input
84 3340591777859038765021667 73 7501655746272260576287 99 44338782446385740696327464779 0 0
Output
20 39 25 26 27 20 33 30 36