== include(page="template/taskheader" task_id="balans2") ==
Poveste şi cerinţă...
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 $)$.
h2. 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.
h2. Date de intrare
Fişierul de intrare $balans2.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $balans2.out$ ...
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.
h2. Restricţii
h2. 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$
h2. Exemplu
table(example). |_. balans2.in |_. balans2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 12
(()P)PPP)(P)
| 000100010001
|
h3. Explicaţie
...
Şirul $S$ ia, pe rând, valorile
$($
$(($
$(()$
$()$
$())$
$))$
$)$
$)$
$)($
$($
$()$
== include(page="template/taskfooter" task_id="balans2") ==
