Fişierul intrare/ieşire:hanoi1.in, hanoi1.outSursă.campion 2003
AutorMarius AndreiAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.6 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

hanoi1.inhanoi1.out
2
2 3
1 2
3 1
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici