Fişierul intrare/ieşire:puzzle.in, puzzle.outSursăBaraj 2008 gimnaziu
AutorLivia TocaAdăugată deraduzerRadu Zernoveanu raduzer
Timp execuţie pe test0.2 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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.

Date de intrare

In fisierul de intrare puzzle.in se afla

  • pe prima linie, cuvantul corect;
  • pe a doua linie, cuvantul format prin asezarea initiala a placutelor.

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.

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.

Exemplu

puzzle.inpuzzle.out
abc
bac
2 0
abcabc
aabbcc
6 2 2 0
xyz
xyz
0

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content