== include(page="template/taskheader" task_id="rebus") ==
Poveste şi cerinţă...
Se dă un rebus orizontal reprezentat ca un grid infinit, o listă de $N$ cuvinte aşezate în grid, fiecare literă ocupând o celulă din grid şi un pattern $P$. Cuvântul $i$ ocupă la început poziţiile $(i, 0) -> (i, |c{~i~}|-1)$, unde $|c{~i~}|$ este lungimea celui de-al $i$-lea cuvânt. Asupra cuvintelor se pot efectua două operaţii:
1. Se alege un cuvânt şi se shiftează cu o poziţie la stânga sau la dreapta, mutare care are cost 1
2. Se aleg două cuvinte şi se interschimbă cele 2 linii care le conţin, păstrând pentru fiecare în parte offseturile la care se aflau înainte de interschimbare, mutare care are cost 0
Se cere costul minim al unui set de mutări în urma căruia patternul $P$ se găseşte pe cel puţin o coloană din grid.
h2. Date de intrare
Fişierul de intrare $rebus.in$ ...
Fişierul de intrare $rebus.in$ conţine pe prima linie un număr natural $T$, reprezentând numărul de teste. Pe următoarele linii sunt cele $T$ teste în următorul format: pe prima linie se află un număr natural $N$, reprezentând numarul de cuvinte din grid. Pe următoarele $N$ linii se găsesc cele $N$ cuvinte, câte unul pe linie. Pe a $N+2$-a linie se gaseşte patternul $P$.
h2. Date de ieşire
În fişierul de ieşire $rebus.out$ ...
Fişierul de ieşire $rebus.out$ va conţine $T$ linii, al $i$-lea număr reprezentând răspunsul pentru testul $i$ sau *-1* dacă nu există soluţie.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 25$
* $1 ≤ |c{~i~}| ≤ 25$
* $|P| = N$
* Cele $N$ cuvinte conţin litere din mulţimea ${a, b, c, d, e, f}$
h2. Exemplu
table(example). |_. rebus.in |_. rebus.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
3
aae
bcbb
edd
eec
| 2
|
h3. Explicaţie
În stânga avem poziţia iniţială a cuvintelor în grid. Prima operaţie pe care o vom efectua este să interschimbăm *bcbb* cu *edd*, a doua operaţie este să shiftăm *aae* cu o pozitie la stânga, iar a treia operaţie este să shiftăm *edd* cu o poziţie la dreapta. În final, costul celor 3 operaţii este $0 + 1 + 1 = 2$, configuraţia finală fiind reprezentată de imaginea din dreapta.
!{width: 500px} problema/rebus?start.png! !{width: 500px}problema/rebus?end.png!
...
== include(page="template/taskfooter" task_id="rebus") ==
