== include(page="template/taskheader" task_id="puzzle") ==
Unul dintre jocurile preferate ale lui Temistocle este un puzzle In care el are la dispozitie un cuvant, fiecare litera a acestuia fiind scrisa pe cate o placuta. Initial, toate placutele sunt amestecate si asezate intr-o ordine oarecare pe un suport liniar, pozitiile placutelor fiind numerotate de la stanga la dreapta, incepand cu 1.
Unul dintre jocurile preferate ale lui Temistocle este un puzzle In care el are la dispozitie un cuvant, fiecare litera a acestuia fiind scrisa pe cate o placuta. Initial, toate placutele sunt amestecate si asezate intr-o ordine oarecare pe un suport liniar, pozitiile placutelor fiind numerotate de la stanga la dreapta, incepand cu $1$.
Daca se alege o placuta drept pivot, se obtin doua grupe:
* grupa 1 - formata din toate placutele din stanga placutei-pivot, inclusiv aceasta;
* grupa 2 - formata din toate placutele din dreapta placutei-pivot, fara aceasta.
Dupa alegerea placutei-pivot, toate placutele din grupa 1, daca exista, se deplaseaza circular spre stanga cu exact o pozitie, iar toate placutele din grupa 2, daca exista, se deplaseaza circular spre dreapta, cu exact o pozitie, ca in figura de mai jos, dupa care placutele se renumeroteaza, de la stanga la dreapta, incepand cu 1.
Scopul jocului este ca prin alegerea unui sir potrivit de placute-pivot sa se obtina o asezare a placutelor, astfel incat cuvântul format din literele scrise pe acestea, de la stanga la dreapta, sa fie identic cu cuvantul corect.
* grupa **1** - formata din toate placutele din stanga placutei-pivot, inclusiv aceasta;
* grupa **2** - formata din toate placutele din dreapta placutei-pivot, fara aceasta.
Dupa alegerea placutei-pivot, toate placutele din grupa $1$, daca exista, se deplaseaza circular spre stanga cu exact o pozitie, iar toate placutele din grupa $2$, daca exista, se deplaseaza circular spre dreapta, cu exact o pozitie, ca in figura de mai jos, dupa care placutele se renumeroteaza, de la stanga la dreapta, incepand cu $1$.
!problema/puzzle?pivot.jpg!
Scopul jocului este ca prin alegerea unui sir potrivit de placute-pivot sa se obtina o asezare a placutelor, astfel incat cuvantul format din literele scrise pe acestea, de la stanga la dreapta, sa fie identic cu cuvantul corect.
h2. Date de intrare
In fisierul de intrare $puzzle.in$ se afl�
* pe prima linie, cuvântul corect;
* pe a doua linie, cuvântul format prin asezarea initiala a placutelor.
In fisierul de intrare $puzzle.in$ se afla
* pe prima linie, cuvantul corect;
* pe a doua linie, cuvantul format prin asezarea initiala a placutelor.
h2. Date de iesire
In fisierul de iesire $puzzle.out$ se vor scrie, separate prin cate un spatiu, numerele naturale, reprezentand pozitiile placutelor-pivot, in ordinea alegerii lor. sirul se incheie cu numarul 0, care nu corespunde niciunei placute, ci reprezinta finalul jocului.
In fisierul de iesire $puzzle.out$ se vor scrie, separate prin cate un spatiu, numerele naturale, reprezentand pozitiile placutelor-pivot, in ordinea alegerii lor. sirul se incheie cu numarul $0$, care nu corespunde niciunei placute, ci reprezinta finalul jocului.
h2. Restrictii
* Fiecare cuvant are cel mult 250 de litere.
* Dac� exist� mai multe soluţii, se va furniza una singur�, nu neap�rat optim�.
* Fiecare cuvant are cel mult $250$ de litere.
* Daca exista mai multe solutii, se va furniza una singura, nu neaparat optima, ce contine cel mult $80.000$ de mutari.
h2. Exemplu
table(example). |_. puzzle.in |_. puzzle.out |
| abc
bac
| $2 0$
| 2 0
|
| abcabc
aabbcc
| $6 2 2 0$
| 6 2 2 0
|
|xyz
xyz
| $0$
| 0
|
h3. Explicatie
...
Exemplul 1:
pivot - $2$
ba | c -> ab | c
Exemplul 2:
pivot - $6$
aabbcc | -> abbcca |
pivot - $2$
ab | bcca -> ba | abcc
pivot - $2$
ba | abcc -> ab | cabc
Exemplul 3:
Cuvantul corespunzator placutelor este cel corect.
== include(page="template/taskfooter" task_id="puzzle") ==
