Fișierul intrare/ieșire	puzzle.in, puzzle.out	Sursă	ONI 2008 baraj gimnaziu
Autor	Livia Țoca	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	1 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Puzzle (baraj gimnaziu)

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.

Cerință

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.

Date de intrare

În fișierul 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.

Date de ieșire

În fișierul de ieșire 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.

Restricții

• Fiecare cuvânt are cel mult 250 de litere.
• Dacă există mai multe soluții, se va furniza una singură, nu neapărat optimă.

Exemplu