hanoi2

Hanoi2

== include(page="template/taskheader" task_id="hanoi2") ==

!{float:right;}problema/hanoi2?infoarena1.png!

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.

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.

 
 
 
!{float:right;}problema/hanoi2?infoarena2.png!

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:

h2. Date de intrare

Fişierul de intrare $hanoi2.in$ ...

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ă.
 

h2. Date de ieşire

În fişierul de ieşire $hanoi2.out$ ...

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.
 

h2. 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
 

h2. Exemplu

table(example). |_. hanoi2.in |_. hanoi2.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

table(example). |_. hanoi2.in |_. hanoi2.out |_. Explicaţie |
| 3
2 3 0
4 7 5 1 9
| 2 3
1 3
2 1
2 3
1 2
1 3
2 3
0 0
| discurile pe cele trei tije sunt:
     *9*
 7    1
 4    5
(1) (2) (3) de la 2 la 3
 
* 7*   1
 4   5   9
(1) (2) (3) de la 2 la 3
 
    * 1*   7
 4   5   9
(1) (2) (3) de la 2 la 3
 
 1       7
 4   *5*   9
(1) (2) (3) de la 2 la 3
 
         5
* 1*       7
 4       9
(1) (2) (3) de la 2 la 3
 
         5
         7
* 4*   1   9
(1) (2) (3) de la 2 la 3
 
         4
         5
         7
    * 1*   9
(1) (2) (3) de la 2 la 3
 
         1
         4
         5
         7
         9
(1) (2) (3) marcaj de sfarsit 0 0
|
 
Următoarele informaţii despre structura fişierelor de intrare vă pot fi utile:
!{display:block; margin-left:auto; margin-right:auto;}problema/hanoi2?infoarena3.png!
 
Semnificaţia simbolurilor este:
 
!{float:left;}problema/hanoi2?infoarena5.png!
 - coloană de discuri ordonate descrescător de jos în sus
 
!{float:left;}problema/hanoi2?infoarena6.png!
  - coloană de discuri ordonate crescător de jos în sus
 
!{float:left;}problema/hanoi2?infoarena7.png!
- coloană de discuri neordonată
 
!{float:left;}problema/hanoi2?infoarena8.png!
   - tijă fără discuri

h3. Explicaţie
...

== include(page="template/taskfooter" task_id="hanoi2") ==