| Fişierul intrare/ieşire: | balans2.in, balans2.out | Sursă | InfoPro, Runda 1, Grupa A |
| Autor | Bogdan Ciobanu | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Balans2
Se consideră un şir iniţial vid pe care vrem să efectuăm Q operaţii de următorul fel:
- se adaugă un caracter la finalul şirului;
- se elimină un caracter de la începutul şirului.
Caracterele vor fi doar paranteze, mai exact, vor fi doar caracterele ( sau ).
Cerinţă
Să se determine după fiecare operaţie dacă secvenţa S formată din elementele şirului formează o parantezare corectă. O secvenţă se consideră parantezată corect dacă se poate transforma într-o expresie aritmetică validă adăugând doar caracterele 1 şi + în secvenţa iniţială. Spre exemplu () şi (()) sunt parantezate corect pentru că putem scrie (1) respectiv ((1+1)+1), în timp ce )() sau ()) nu sunt. Şirul vid se consideră de asemenea corect parantezat.
Date de intrare
Din fişierul de intrare balans2.in se va citi pe prima linie Q, reprezentând numărul de operaţii.
Pe a doua linie se vor găsi Q caractere fără spaţii intre ele de trei tipuri:
- ( înseamnă că se cere adăugarea caracterului ( la finalul şirului.
- ) înseamnă că se cere adăugarea caracterului ) la finalul şirului.
- P înseamnă că se va elimina caracterul de la începutul şirului.
Date de ieşire
Pe ecran se vor afişa Q caractere, fără spaţii între ele, câte unul după fiecare operaţie, codificate în felul următor:
- 0 înseamnă că în urma operaţiei şirul nu este corect parantezat.
- 1 înseamnă că în urma operaţiei şirul este corect parantezat.
Restricţii şi precizări
- 1 ≤ Q ≤ 2.000.000.
- Se garantează, că pentru fiecare P citit, şirul conţine cel puţin o paranteză ce se poate şterge.
- Pentru 13 puncte, nu exista P in datele de intrare.
- Pentru alte 21 puncte, Q ≤ 2.000
- Pentru alte 24 puncte, Q ≤ 100.000
Exemplu
| balans2.in | balans2.out |
|---|---|
| 12 (()P)PPP)(P) | 000100010001 |
Explicaţie
Şirul S ia, pe rând, valorile
(
((
(()
()
())
))
)
)
)(
(
()
