== include(page="template/taskheader" task_id="puzzle") ==
Unul dintre jocurile preferate ale lui Temistocle este un puzzle în care el are la dispoziţie un cuvânt, fiecare literă a acestuia fiind scrisă pe câte o plăcuţă. Iniţial, toate plăcuţele sunt amestecate şi aşezate într-o ordine oarecare pe un suport liniar, poziţiile plăcuţelor fiind numerotate de la stânga la dreapta, începând cu 1.
Dacă se alege o plăcuţă drept pivot, se obţin două grupe:
* grupa 1 - formată din toate plăcuţele din stânga plăcuţei-pivot, inclusiv aceasta;
* grupa 2 - formată din toate plăcuţele din dreapta plăcuţei-pivot, fără aceasta.
După alegerea plăcuţei-pivot, toate plăcuţele din grupa 1, dacă există, se deplasează circular spre stânga cu exact o poziţie, iar toate plăcuţele din grupa 2, dacă există, se deplasează circular spre dreapta, cu exact o poziţie, ca în figura de mai jos, după care plăcuţele se renumerotează, de la stânga la dreapta, începând 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:
Scopul jocului este ca prin alegerea unui şir potrivit de plăcuţe-pivot să se obţină o aşezare a plăcuţelor, astfel încât cuvântul format din literele scrise pe acestea, de la stânga la dreapta, să fie identic cu cuvântul 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 aşezarea iniţială a plăcuţelor.
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 câte un spaţiu, numerele naturale, reprezentând poziţiile plăcuţelor-pivot, în ordinea alegerii lor. Şirul se încheie cu numărul 0, care nu corespunde niciunei plăcuţe, ci reprezintă 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") ==
