Puzzle

puzzle

== 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$.
 
!problema/puzzle?pivot.jpg!

* 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 cuvantul format din literele scrise pe acestea, de la stanga la dreapta, sa fie identic cu cuvantul corect.

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.
* Daca exista mai multe solutii, se va furniza una singura, nu neaparat optima, ce contine cel mult $80.000$ de mutari.

* Fiecare cuvant are cel mult 250 de litere.
* Daca exista mai multe solutii, se va furniza una singura, nu neaparat optima.

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$

pivot - 2

ba | c -> ab | c
Exemplul 2:

pivot - $6$

pivot - 6

aabbcc | -> abbcca |

pivot - $2$

pivot - 2

ab | bcca -> ba | abcc

pivot - $2$

pivot - 2

ba | abcc -> ab | cabc
Exemplul 3:

Cuvantul corespunzator placutelor este cel corect.

Cuv�¢ntul corespunzator placutelor este cel corect.

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

2809