Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | par.in, par.out | Sursă | Algoritmiada 2009, Runda 3 |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Par
Ioana tocmai a invatat la scoala despre paranteze rotunde si despre siruri parantezate corect. Un sir este parantezat corect daca este construit conform regulilor:
- <sir parantezat corect> = <sirul vid>
- <sir parantezat corect> = "(" + <sir parantezat corect> + ")"
- <sir parantezat corect> = <sir parantezat corect> + <sir parantezat corect>
De exemplu (()) si ()() sunt siruri parantezate corect, dar )() sau (()( nu sunt parantezate corect. Andrei i-a furnizat Ioanei un sir format din N paranteze inchise sau deschise si ea se gandeste acum sa inverseze unele paranteze (sa schimbe o paranteza deschisa cu una inchisa sau invers) astfel incat la final sirul sa fie parantezat corect. Ajutati-o pe Ioana si determinati numarul minim de inversari care trebuie efectuat astfel incat la final sirul sa fie parantezat corect.
Date de intrare
Fişierul de intrare par.in contine pe prima linie numarul natural N, avand semnificatia din enunt. Pe a doua linie urmeaza N caractere reprezentand sirul de paranteze furnizat de Andrei.
Date de ieşire
În fişierul de ieşire par.out se va afisa un singur numar, reprezentand numarul minim de inversari ce trebuie efectuat pentru ca la sfarsit sirul sa fie corect parantezat. In cazul in care nu exista solutie se va afisa doar numarul -1.
Restricţii
- 1 ≤ N ≤ 5000
Exemplu
| par.in | par.out |
|---|---|
| 4 ((() | 1 |
Explicaţie
Se inverseaza a treia paranteza si sirul devine (()), care este un sir corect parantezat.
