Fişierul intrare/ieşire:parola.in, parola.outSursăACM ICPC Faza Nationala 2015
AutorSteve DowningAdăugată deneapuiuComisie ICPC UPB neapuiu
Timp execuţie pe test2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Parola

Fane Babanu incearca sa apare Iasiul si concurentii de la ACM de un nou atac. Cum vremurile s-au schimbat atacul este electronic de aceasta data. Pentru a putea apara Iasiul Fane trebuie sa sparga o parola. Dupa indelungi eforturi el a reusit sa afle ca parola este un text scris cu litere mici in alfabetul latin 'a'-'z', pentru care suma codurilor ascii % N este egala cu K. Fane a reusit sa obtina si un text si stie ca parola se afla in acel text dar nu stie intre care pozitii. Pentru a putea gasi parola el va putea folosi oricati plăieşi care vor încerca fiecare o parolă în acelasi timp, totuşi el vrea să reducă numărul de plăieşi folositi la minim. Ajutati-l pe Stefan spunandu-i cate parole se gasesc in textul dat. Fane are de spart maxim T parole.

Date de intrare

Fişierul de intrare parola.in are pe prima linie T numarul de parole. Urmeaza T teste fiecare pe 2 randuri. Pe primul rand a unui test se vor afla N si K pe urmatorul aflandu-se textul.

Date de ieşire

În fişierul de ieşire parola.out, pentru fiecare test pe un rand se va afla un numar reprezentand numarul de parole posibile in fiecare din teste.

Restricţii si observatii

  • 1 ≤ T ≤ 15
  • 1 ≤ N ≤ 1000000
  • 0 ≤ K < N
  • 1 ≤ L(text) ≤ 1000000

Doua parole vor fi considerate distincte daca sunt intre doi indici diferiti!
Parola vida nu este considerata o parola valida.

Exemplu

parola.inparola.out
2
195 0
abc
196 0
bacbxxbbxxbbb
1
5

Explicaţie

In primul test singura solutie este ab
In al doilea test solutiile sunt bacb, ac, bb(6-7), bb(10-11), bb(11-12)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?