Puzzle

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

* grupa <b>1</b> - formata din toate placutele din stanga placutei-pivot, inclusiv aceasta;
* grupa <b>2</b> - 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$.

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.

* Daca exista mai multe solutii, se va furniza una singura, nu neaparat optima.

h2. Exemplu

Cuvantul corespunzator placutelor este cel corect.
== include(page="template/taskfooter" task_id="puzzle") ==

2809