secvreg
Sa
consideram secvente constituite numai din paranteze rotunde si paranteze
patrate, adica din caracterele ( ) [
].
Prin definitie, o secventa de paranteze este regulata daca
se obtine aplicand urmatoarele reguli:
1.() si [] sunt secvente regulate.
2. Daca
A este regulata, atunci (A) si [A] sunt secvente regulate.
3. Daca
A si B sunt regulate, atunci AB este secventa regulata.
De
exemplu, () () [] si [(())][] sunt regulate, in timp ce
][ sau [(] sau([)] nu sunt regulate.
Se considera
o secventa de paranteze.
La fiecare pas se insereaza o paranteza (rotunda sau
patrata, deschisa sau inchiss) la inceputul sau la sfarsitul secventei.
Cerinta
Scrieti un program care sa determine, dupa fiecare pas, lungimea celei mai scurte subsecvente regulate (formata din caractere consecutive ale secventei) care contine paranteza inserata la pasul respectiv.
Date de
intrare
Fisierul de intrare secvreg.in contine pe prima linie
secventa initiala de paranteze. Pe cea de a doua linie a fisierului de intrare
se afla un numar natural N care
reprezinta numarul de pasi.
Fiecare dintre urmatoarele N linii contine un numar natural A si un caracter C separate printr-un singur spatiu.
Daca A este 0 (zero) atunci caracterul C este inserat la inceputul secventei;
daca A este 1 (unu) atunci caracterul C este inserat la sfarsitul secventei.
Date de
iesire
Fisierul de iesire secvreg.out contine N linii. Pe cea de a i-a linie va fi afisata lungimea celei mai scurte subsecvente regulate (formata din caractere consecutive ale secventei) care contine paranteza inserata la pasul i. Daca nu exista o astfel de subsecventa, pe linia respectiva veti afisa 0.
Restrictii
Lungimea secventei
initiale de paranteze <=100
000
1<=N<=100
000
Exemple
secvreg.in | secvreg.out | secvreg.in | secvreg.out | secvreg.in | secvreg.out |
( |
2 | (] 3 1 ) 0 ) 0 ( |
0 0 2 |
[]) 3 0 ) 0 ( 0 ( |
0 |
Timp maxim de executie/test: 0.1 secunde
prof.
Emanuela Cerchez
Liceul de Informatica "Grigore Moisil"
Iasi
Contact:ema at
mail.dntis.ro