Algorithmen Übungen WS 2008/2009

Sabrina löst gerne Puzzle. Ihr neuestes Puzzle heißt "die Türme von Hanoi". Dabei handelt es sich um ein Spiel mit 3 Holzstäben und n unterschiedlich großen Scheiben mit kreisförmigen Öffnungen in der Mitte. Die Scheiben können auf den Holzstäben aufgeschichtet werden, wobei nie eine kleinere Scheibe unter einer größeren Scheibe liegen darf. Am Anfang des Spieles liegen alle Scheiben auf dem ersten Holzstab. Ziel des Spieles ist es, alle Scheiben vom ersten Stab auf den zweiten Stab zu bringen, wobei in jedem Schritt immer nur die oberste Scheibe von einem Stab auf einen Stab gelegt werden darf, der bisher keine kleinere Scheibe enthält.

Sabrina hat das Puzzle bisher schon durchgespielt mit 3 Scheiben, und brauchte dafür 7 Schritte. Mit 4 Scheiben brauchte sie 15 Schritte. Zuletzt startete sie ein Spiel mit 31 Scheiben, aber selbst nach vielen Stunden Spiel war noch kein Ende abzusehen, also ging sie erstmal schlafen. Ihr Bruder Robin stolperte im Dunkeln gegen die Stäbe, und alle Scheiben fielen durcheinander. Er entdeckte ein Stück Papier, auf dem stand: "Bitte nicht berühren! Anzahl Schritte: 16543". "Ha noi!" rief Robin aus, denn ihm war klar, wenn es ihm nicht gelänge, die Türme zu rekonstruieren, würde seine Schwester sehr böse werden.

Ihre Aufgabe ist es, Robin dabei zu helfen, die Türme zu rekonstruieren. Hierbei wird angenommen, dass Sabrina die optimale Strategie verfolgte, um die Scheiben von dem ersten auf den zweiten Stab zu bringen.

Eingabe

Die Eingabe besteht aus einer Zeile mit zwei Zahlen n (2 ≤ n ≤ 31) und k (0 < k < 2ⁿ). n ist die Anzahl der Scheiben, und k ist die Anzahl an Schritten, die Sabrina bisher durchgeführt hat.

Ausgabe

Geben Sie den Zustand der Türme nach k Schritten aus. Der Zustand soll wie folgt beschrieben werden: nummerieren Sie die aufsteigend nach Größe sortierten Scheiben von 1 bis n. Geben Sie n Zeilen aus, wobei die i-te Zeile den Index desjenigen Stabes enthält, auf dem die Scheibe mit der Nummer i liegt.

Beispiel 1

Eingabe:
3 7
Ausgabe:
2
2
2

Beispiel 2

Eingabe:
31 16543
Ausgabe:
2
2
2
2
2
1
1
2
3
3
3
3
3
3
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

Achtung! naive Simulation in O(k) ist zu langsam.