Fişierul intrare/ieşire: | paranteze2.in, paranteze2.out | Sursă | Infoarena Monthly 2012, Runda 1 |
Autor | Andrei Cristian Lambru | Adăugată de | |
Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Paranteze2
Se da un sir de caractere S, de lungime N, ce poate contine caracterele '(' si ')' . Sa se calculeze si sa se afiseze cate subsecvente ale lui S reprezinta parantezari corecte.
Se numeste o parantezare corecta un sir T de paranteze daca se poate forma astfel:
T = '()'
sau
T = '(' + t + ')' , unde t este o parantezare corecta
sau
T = t1+ t2 +...+tn , unde t1, t2, ..., tn sunt parantezari corecte.
Date de intrare
Fişierul de intrare paranteze2.in va contine pe prima si unica sa linie sirul S.
Date de ieşire
În fişierul de ieşire paranteze2.out se va scrie numarul subsecventelor ce constituie parantezari corecte.
Restricţii
- 1 ≤ N ≤ 1.000.000
- se intelege subsecventa a sirului S un interval compact de forma [i..j] cu 1 ≤ i ≤ j ≤ N
Exemplu
paranteze2.in | paranteze2.out |
---|---|
()(()) | 4 |
Explicaţie
Cele 4 subsecvente sunt 1-2, 3-6, 4-5 si 1-6