| Fişierul intrare/ieşire: | sabin.in, sabin.out | Sursă | ONI 2015, Baraj |
| Autor | Andrei Ciocan, Andrei Parvu, Eugenie Daniel Posdarascu, Vlad Ionescu | Adăugată de |  Tudor Tiplea •tzipleatud |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/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
Fişierul sabin.out va conţine Q linii, câte una pentru fiecare întrebare din fişierul de intrare, reprezentând numărul de compartimente din primul raft care satisfac cerinţa dată.
Restricţii
- 1 ≤ N ≤ 20 000
- 1 ≤ M ≤ 30 000
- 1 ≤ Q ≤ 20 000
- 1 ≤ K ≤ 15
- 1 ≤ P ≤ 30
- 0 ≤ X ≤ 30
Exemplu
| sabin.in | sabin.out |
|---|---|
| 4 2 6 4 4 abcd trzs gefd fasf gefa fasx fxxx txxx affx trfs abxx trxx gefa fasf 1 1 2 1 3 4 3 5 6 1 6 2 | 1 0 2 1 |
Explicaţie
Numerele de pe prima linie a fişierului de intrare reprezintă N = 4, K = 2, M = 6, P = 4 şi Q = 4.
Primul raft este format din N = 4 compartimente. Fiecare compartiment are K = 2 cărţi, formate din P = 4 caractere: [abcd, trzs] [gefd, fasf] [gefa, fasx], [fxxx, txxx].
Avem M = 6 cărţi pe al doilea raft: affx, trfs, abxx, trxx, gefa, fasf.
Primul query cere numărul de compartimente care să aibă coeficientul de similitudine cu [affx, trfs] egal cu 1. Doar compartimentul [abcd, trzs] satisface cerinţa.
Al doilea query cere numărul de compartimente care să aibă coeficientul de similitudine cu [abxx, trxx] egal cu 1. Nu există niciun astfel de compartiment. Compartimentul [abcd, trzs] are gradul de similitudine 2.
Al treilea query cere numărul de compartimente care să aibă coeficientul de similitudine cu [gefa, fasf] egal cu 3. Soluţia este [gefd, fasf] şi [gefa, fasx].
Al patrulea query cere numărul de compartimente care să aibă coeficientul de similitudine cu [fasf, trfs] egal cu 1. Soluţia este [fxxx, txxx].
