Fişierul intrare/ieşire:	hanoi2.in, hanoi2.out	Sursă	ProSoft@NT 2017
Autor	Zoltan Szabo	Adăugată de	Valentin Rosca •valiro21
Timp execuţie pe test	4.5 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Hanoi2

Turnurile din Hanoi este un joc matematic. Este format din trei tije şi un număr variabil de discuri, de diferite mărimi, care pot fi poziţionate pe oricare din cele 3 tije. Jocul începe având discurile aşezate în stivă pe prima tijă, în ordinea mărimii lor, astfel încât să formeze un turn. Scopul jocului este acela de a muta întreaga stivă de pe o tijă pe alta, respectând următoarele reguli:

• Doar un singur disc poate fi mutat, la un moment dat.
• Fiecare mutare constă în luarea celui mai de sus disc de pe o tija şi glisarea lui pe o altă tijă, chiar şi deasupra altor discuri care sunt deja prezente pe acea tijă.
• Un disc mai mare nu poate fi poziţionat deasupra unui disc mai mic. (Wikipedia)

Gigel este pasionat de informatică. Chiar de aceea, când au învăţat algoritmul turnurilor din Hanoi la şcoală, tatăl său l-a surprins cu un joc Hanoi, constând din trei tije şi mai multe discuri de dimensiuni diferite. Astfel Gigel nu numai că a scris un program ce rezolvă problema, dar poate să şi verifice corectitudinea acestuia.

Fratele său mai mic, Petrică, dornic să încerce şi el noul joc, s-a apucat să mute discurile pe tijă, fără să ţină cont
de regulile descrise mai sus. Astfel a reuţit să încurce ordinea discurilor. Dar Gigel nu s-a supărat. A inventat
următorul joc:
„Avem un joc Hanoi încurcat, să grupăm toate discurile pe o tijă precizată, în ordinea mărimii lor, folosind toate regulile jocului Turnurilor din Hanoi.”

Date de intrare

Fişierul hanoi.in are următoarea structură:

• Pe prima linie un număr natural d. Valori posibile 1, 2 sau 3 şi reprezintă numărul tijei destinaţie, pe care se vor grupa discurile în final în ordinea mărimii lor.
• Pe a doua linie trei numere naturale n1 n2 n3 separate prin câte un spaţiu, reprezentând numărul de discuri existente pe tija 1, tija 2 respectiv tija 3.
• Pe a treia linie n1+n2+n3 numere naturale separate prin câte un spaţiu. Primele n1 numere reprezintă dimensiunea discurilor de pe prima tijă. Următoarele n2 numere reprezintă dimnesiunea discurilor de pe a doua tijă, iar următoarele n3 numere reprezintă discurile de pe ultima tijă. Discurile sunt enumerate începând de la bază.

Date de ieşire

Fişierul hanoi.out are următoarea structură:

Pe fiecare linie a fişierului se va scrie câte o mutare în ordinea efectuărilor lor. Fiecare mutare constă dintr-o pereche de numere naturale a b cu semnificaţia: „discul din vârful tijei a se mută pe tija b”
Pe ultima linie a fişierului de ieşire se va tipări perechea de numere 0 0.

Restricţii

• 1 ≤ a, b, d ≤ 3
• 1 ≤ dimensiunea unui disc ≤ 32000
• 2 ≤ n1+n2+n3 ≤ 18
• În configuraţia iniţială, pot fi şi tije goale, adică valorile n1, n2, n3 pot avea valoare 0.
• Rezolvarea problemei nu este unică. Se acceptă orice soluţie corectă, chiar dacă există mutări inutile. De exemplu:
  • a b urmat de b a
  • a a

Exemplu

Următoarele informaţii despre structura fişierelor de intrare vă pot fi utile:

Semnificaţia simbolurilor este:

 - coloană de discuri ordonate descrescător de jos în sus
 
  - coloană de discuri ordonate crescător de jos în sus
 
- coloană de discuri neordonată
 
   - tijă fără discuri

Cum se trimit solutii?