Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | rebus.in, rebus.out | Sursă | Romanian Collegiate Programming Contest 2019 |
| Autor | Cristi Banu, Radu Visan | Adăugată de |  RCPC2019 •RCPC2019 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Rebus
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, |ci|-1), unde |ci| 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.
Date de intrare
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.
Date de ieşire
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.
Restricţii
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 25
- 1 ≤ |ci| ≤ 25
- |P| = N
- Cele N cuvinte conţin litere din mulţimea {a, b, c, d, e, f}
Exemplu
| rebus.in | rebus.out |
|---|---|
| 1 3 aae bcbb edd eec | 2 |
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.
...
