Torres de Hanoi adjacents P75664

Statement

Les torres de Hanoi és un joc consistent en tres pals i $n$ discs de mides diferents que es poden fer lliscar per cada pal. El joc comença amb els discs en el pal de l’esquerra, empilats ordenadament amb el més gran al fons. L’objectiu del joc és moure tots els discs del pal de l’esquerra (pal A) al pal de la dreta (pal C), utilitzant el pal del mig (pal B) com a pal auxiliar. Els moviments han de seguir les regles següents:

Només es pot moure un sol disc a cada pas.
Cada moviment consisteix a agafar el disc superior d’un dels tres pals i moure’l a sobre de tots els discs d’un altre pal.
No es pot col·locar cap disc a sobre d’un de més petit.

Considereu una variant d’aquest joc, amb una restricció afegida:

Només es poden moure discs entre pals adjacents. És a dir, els moviments A => C i C => A estan prohibits.

Feu un programa que resolgui aquesta variant de les torres de Hanoi, amb el mínim nombre de moviments possibles.

Entrada

L’entrada consisteix en diversos naturals $n$ entre 1 i 11.

Sortida

Per a cada $n$ , escriviu la seqüència més curta de moviments (en té $3^n - 1$ ). Escriviu una línia amb 10 guions al final de cada cas.

Public test cases

Input

1
2
3

Output

A => B
B => C
----------
A => B
B => C
A => B
C => B
B => A
B => C
A => B
B => C
----------
A => B
B => C
A => B
C => B
B => A
B => C
A => B
B => C
A => B
C => B
B => A
C => B
A => B
B => C
B => A
C => B
B => A
B => C
A => B
B => C
A => B
C => B
B => A
B => C
A => B
B => C
----------

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++ Python