Fişierul intrare/ieşire:balans2.in, balans2.outSursăInfoPro, Runda 1, Grupa A
AutorBogdan CiobanuAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test0.2 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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:

  1. ( înseamnă că se cere adăugarea caracterului ( la finalul şirului.
  2. ) înseamnă că se cere adăugarea caracterului ) la finalul şirului.
  3. 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:

  1. 0 înseamnă că în urma operaţiei şirul nu este corect parantezat.
  2. 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.inbalans2.out
12
(()P)PPP)(P)
000100010001

Explicaţie

Şirul S ia, pe rând, valorile

(
((
(()
()
())
))
)
)
)(
(
()

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?