Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | constant.in, constant.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" |
Autor | George Marcus | Adăugată de | |
Timp execuţie pe test | 0.75 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
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 3-4 si 1-5 in sir).
Pe o portiune de drum se aplica ultimul semn de inceput de zona intalnit. Formal, intre kilometrul i si i + 1 viteza maxima e Sj, astfel incat j e maxim si Sj e cifra. Se garanteaza ca tot timpul va exista un astfel de j.
Se dau 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 raspundeti 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
- 2 ≤ N, 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 1 - N+1 din sir
Exemplu
constant.in | constant.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:
Interval | Viteza maxima |
---|---|
0 - 1 | 1 |
1 - 2 | 1 |
2 - 3 | 9 |
3 - 4 | 1 |
Pentru a face viteza constanta intre kilometrii 1 - 3, trebuie sa eliminam perechea de semne care restrictioneaza viteza la 9.