Fişierul intrare/ieşire:rebus.in, rebus.outSursăRomanian Collegiate Programming Contest 2019
AutorCristi Banu, Radu VisanAdăugată deRCPC2019RCPC2019 RCPC2019
Timp execuţie pe test0.3 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/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.inrebus.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.


...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?