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
De la tastatură 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 * 106
Se garantează, că pentru fiecare P citit, șirul conține cel puțin o paranteză ce se poate șterge.
Subtask 1 (13 puncte): Nu exista P in datele de intrare.
Subtask 2 (21 puncte): Q ≤ 2000
Subtask 3 (24 puncte): Q ≤ 105
Subtask 4 (42 puncte): Fără restricții suplimentare.
Exemplu
Intrare
12
(()P)PPP)(P)
Iesire
000100010001
Răspunsuri la întrebare
Răspuns:
#include <iostream>
#include <deque>
using namespace std;
//ifstream cin ("balans.in");
//ofstream cout ("balans.out");
deque <int> dq, a;
bool mere()
{
a=dq;
long long int suma=0;
while(!a.empty())
{
suma += a.front();
if(suma < 0)
return 0;
a.pop_front();
}
return 1;
}
int main()
{
long long int Q, suma = 0, tip_paranteza, nr_elemente=0;
long long int i;
char ch,ult_paranteza = '2';
cin >> Q;
for( i = 1 ; i <= Q ; i ++)
{
cin>>ch;
if(ult_paranteza == ch && nr_elemente)
{
if(ch=='(')
tip_paranteza = 1;
else
tip_paranteza = -1;
dq[dq.size()-1] += tip_paranteza;
suma += tip_paranteza;
nr_elemente++;
}
else
{
if(ch == 'P')
{
if(nr_elemente)
{
int a=dq.front();
if (a >= 1)
{
dq.front() = a-1;
suma -= 1;
}
else
{
if (a <= -1)
{
dq.front () = a+1;
suma += 1;
}
}
if(dq.front() == 0)
dq.pop_front();
nr_elemente--;
}
}
else
{
if(ch=='(')
tip_paranteza = 1;
else
tip_paranteza = -1;
dq.push_back(tip_paranteza);
suma += tip_paranteza;
ult_paranteza = ch;
nr_elemente++;
}
}
if(suma!=0)
cout<<0;
else
{
if(mere())
cout<<1;
else
cout<<0;
}
//cout<<suma<<'\n';
}
return 0;
}
Explicație: