Fișierul intrare/ieșire	hanoi1.in, hanoi1.out	Sursă	.campion 2003
Autor	Marius Andrei	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.6 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Hanoi1 ( clasele 7/8 )

Notă: această problemă a fost simplificată pentru a ajunge la nivel de gimnaziu. Mai exact limita lui N a fost micșorată, iar numărul de mutări și timpul au fost mărite.

Consideram ca avem 3 stalpi (numerotati 1, 2, 3) si 2N discuri. N discuri sunt albe si au dimensiunile diametrelor distincte, cuprinse intre 1 si N. Celelalte N discuri sunt negre si au de asemenea dimensiunile diametrelor distincte, cuprinse intre 1 si N. Aceste discuri sunt asezate pe primii doi stalpi (N pe stalpul 1 si N pe stalpul 2), in ordine strict descrescatoare a dimensiunii diametrelor, in culori alternante.

De exemplu pentru N = 3 pe primul stalp vom avea (de jos in sus): discul de dimensiune 3 alb, discul de dimensiune 2 negru, discul de dimensiune 1 alb. Iar pe stalpul 2: discul de dimensiune 3 negru, discul de dimensiune 2 alb si discul de dimensiune 1 negru.

Mutarile permise sunt mutarea unui disc din varful unui stalp pe alt stalp (tot in varf), cu conditia ca discul peste care se muta sa aiba dimensiune cel putin egala cu a celui mutat. Intrucat exista cate doua discuri de aceeasi dimensiune, acestea pot fi puse oricum unul peste altul.

Cerință

Scrieti un program care sa determine un sir de mutari dupa a caror executare pe un stalp sa se afle N discuri albe, pe unul N discuri negre, iar unul sa fie gol.

Date de intrare

Pe prima linie a fisierului de intrare hanoi1.in este scris N.

Date de ieșire

Fișierul de ieșire hanoi1.out va contine o succesiune de mutari, cate o mutare pe linie. O mutare este descrisa de o pereche de numere naturale separate printr-un spatiu; primul numar este stalpul de pe care se ia discul, iar al doilea numar este stalpul pe care se pune discul. Aceste doua numere pot fi numai 1, 2 sau 3.

Pe ultima linie a fisierului de iesire va fi trecut numarul 0, care semnifica terminarea mutarilor.

Restricții

• 1 ≤ N ≤ 10
• Nu trebuie numar minim de mutari insa numarul de mutari trebuie sa fie de maxim 650 000

Exemplu