== include(page="template/taskheader" task_id="constant") ==
Poveste şi cerinţă...
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 $S[~i~]$ e cifra $(1-9)$, inseamna ca incepe o zona in care viteza maxima e restrictionata la $S[~i~]$;
* Daca $S[~i~]$ e $')'$, inseamna sfarsitul restrictiei anterioare (care nu are pereche);
* Daca $S[~i~]$ 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.
h2. Date de intrare
Fişierul de intrare $constant.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $constant.out$ ...
Î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.
h2. 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$
h2. Exemplu
table(example). |_. constant.in |_. constant.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
4 4
1*9))
1 3
1 2
0 4
3 4
5 1
55)5))
0 5
| 1
0
1
0
0
|
h3. Explicaţie
...
Limitele de viteza din primul exemplu sunt urmatoarele:
table(explanation). |_. Interval |_. Limita de viteza |
| $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$.
== include(page="template/taskfooter" task_id="constant") ==
== include(page="template/taskfooter" task_id="constant") ==
