Fişierul intrare/ieşire:constant.in, constant.outSursăConcursul National de Informatica "Adolescent Grigore Moisil"
AutorGeorge MarcusAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Constant

Georgel se plimba cu masina pe un drum marcat din kilometru in kilometru. Calatoria lui incepe de la kilometrul 0 si merge pana la kilometrul N. La fiecare kilometru i, el noteaza ce semn de circulatie vede. Notitele lui Georgel pot fi reprezentate ca un sir de caractere S de lungime N + 1 astfel incat:

  • Daca Si e cifra (1-9), inseamna ca incepe o zona in care viteza maxima e restrictionata la Si;
  • Daca Si e ')', inseamna sfarsitul restrictiei anterioare (care nu are pereche);
  • Daca Si e '*', inseamna ca nu exista niciun semn la kilometrul i.

Deci, notitele lui Georgel pot fi reprezentate ca un sir de caractere cum ar fi "1*9))". Fiecare inceput de zona va avea o pereche corespondenta sfarsit de zona (pozitiile 2-3 si 0-4 in sir). Intre kilometrii i si i+1 se aplica restrictia impusa de ultimul semn (cu indicele ≤ i) caruia nu i-am intalnit perechea de sfarsit (verificati exemplul pentru clarificare).

Georgel isi pune Q intrebari de forma "Care este numarul minim de perechi corespondente de semne ce trebuie eliminate astfel incat limita de viteza intre kilometrii a si b sa fie constanta?" si voi trebuie sa il ajutati sa raspunda la ele.

Date de intrare

Fişierul de intrare constant.in va contine pe prima linie un numar intreg T, reprezentand numarul de teste. Pe prima linie a fiecarui teste se vor afla doua numere intregi N si Q cu semnificatia din enunt. A doua linie va contine sirul S. Urmatoarele Q linii vor contine cate doua numere intregi separate prin cate un spatiu, a si b. Intre teste va exista cate o linie goala.

Date de ieşire

În fişierul de ieşire constant.out se vor gasi raspunsurile la intrebari. Pentru fiecare test, vor fi afisate raspunsurile pe cate o linie, in ordinea din input. Intre teste se va afisa cate o linie goala.

Restricţii

  • Pentru toate testele de la evaluare T = 10
  • 1 ≤ N ≤ 100000
  • 1 ≤ Q ≤ 100000
  • 0 ≤ a < b ≤ N
  • S ca incepe cu o cifra si se va termina cu un caracter ')'
  • S nu va contine cifra 0
  • Nu este permisa eliminarea perechii de semne de pe pozitiile 0 - N din sir (fiindca ar exista portiuni din drum fara restrictii)
  • Sumele totale ale N-urilor si ale Q-urilor nu vor depasi 500000

Exemplu

constant.inconstant.out
2
4 4
1*9))
1 3
1 2
0 4
3 4
 
5 1
55)5))
0 5
1
0
1
0
 
0

Explicaţie

Limitele de viteza din primul exemplu sunt urmatoarele:

IntervalLimita de viteza
0 - 11
1 - 21
2 - 39
3 - 41

Pentru a face viteza constanta intre kilometrii 1 - 3, trebuie sa eliminam perechea de semne care restrictioneaza viteza la 9.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?