Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-04-08 15:46:20.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:sabin.in, sabin.outSursăONI 2015, Baraj
AutorAndrei Ciocan, Andrei Parvu, Eugenie Daniel Posdarascu, Vlad IonescuAdăugată detzipleatudTudor Tiplea tzipleatud
Timp execuţie pe test0.75 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sabin

Dat fiind ca mallu' nu era cea mai apropiată locaţie, Sabin s-a hotărât să petreacă ceva timp la bibliotecă. Aici el a dat peste două rafturi cu cărţi.

Primul raft conţine N compartimente de cărţi, fiecare compartiment având acelaşi număr de
cărţi, K. Cel de-al doilea raft conţine un singur compartiment cu M cărţi. Toate cărţile din ambele rafturi au titlurile formate din exact P caractere mici ale alfabetului englez.

Un prefix al unui şir de caractere se defineşte ca o subsecvenţă a şirului care începe de pe prima poziţie a acestuia. Definim cel mai mare prefix comun ($maxprefix$) a două şiruri de caractere ca fiind lungimea celei mai lungi secvenţe de caractere care este prefix şi al primului şir şi al celui de-al doilea.

Fiind date două compartimente de titluri de cărti A=[c1, c2, ..., cK] şi B=[d1, d2, ..., dK] definim gradul de similitudine al acestora ca fiind
min(maxprefix(c1, d1), maxprefix(c2, d2), …, maxprefix(cK, dK)).

Sabin ar dori să scoată K cărţi din al doilea raft şi să găsească un compartiment din primul raft pentru care gradul de similitudine să aibă o valoare dată.

Ca să intraţi în graţiile lui Sabin având la dispozitie cele două rafuri de cărţi, trebuie să răspundeţi la Q întrebări de forma: “Fiind date K cărţi din al doilea raft, găsiţi toate compartimentele din primul raft care au gradul de similitudine cu compartimentul dat exact X şi afişaţi numărul lor”.

Date de intrare

Pe prima linie a fişierului sabin.in se află N, K, M, P şi Q. Următoarele N linii descriu mulţimile de cărţi din primul raft: cea de-a i-a linie va conţine K şiruri de caractere de lungime P, despărţite printr-un spaţiu, reprezentând cărţile din cel de-al i-lea compartiment. Următoarea linie descrie cele M cărţi din al doilea raft.

Următoarele Q linii vor conţine fiecare K + 1 numere. Primul număr reprezintă gradul de similitudine dorit X. Următoarele K numere reprezintă indicii cărţilor din al doilea raft care formează noul compartiment.

Date de ieşire

În fişierul de ieşire sabin.out ...

Restricţii

  • ... ≤ ... ≤ ...

Exemplu

sabin.insabin.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?