Fişierul intrare/ieşire:puzzle.in, puzzle.outSursăONI 2008 baraj gimnaziu
AutorLivia TocaAdăugată defrancuCristian Francu francu
Timp execuţie pe test1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

puzzle.inpuzzle.outExplicaţii
abc
bac
2 0
pivot - 2
ba:c -> ab:c
abcabc
aabbcc
6 2 2 0
pivot - 6
aabbcc: -> abbcca:
pivot - 2
ab:bcca -> ba:abcc
pivot - 2
ba:abcc -> ab:cabc
xyz
xyz
0
Cuvântul corespunzător plăcuţelor este cel corect.
Trebuie sa te autentifici pentru a trimite solutii. Click aici