.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » secvreg

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
secvreg


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Sa consideram secvente constituite numai din paranteze rotunde si paranteze patrate, adica din caracterele ( ) [ ].
Prin definitie, o secventa de paranteze este regulata daca se obtine aplicand urmatoarele reguli:
1.() si [] sunt secvente regulate.
2. Daca A este regulata, atunci (A) si [A] sunt secvente regulate.
3. Daca A si B sunt regulate, atunci AB este secventa regulata.
De exemplu, () () [] si [(())][] sunt regulate, in timp ce ][ sau [(] sau([)] nu sunt regulate.
Se considera o secventa de paranteze.
La fiecare pas se insereaza o paranteza (rotunda sau patrata, deschisa sau inchiss) la inceputul sau la sfarsitul secventei.

Cerinta

Scrieti un program care sa determine, dupa fiecare pas, lungimea celei mai scurte subsecvente regulate (formata din caractere consecutive ale secventei) care contine paranteza inserata la pasul respectiv.

Date de intrare


Fisierul de intrare secvreg.in contine pe prima linie secventa initiala de paranteze. Pe cea de a doua linie a fisierului de intrare se afla un numar natural N care reprezinta numarul de pasi.
Fiecare dintre urmatoarele N linii contine un numar natural A si un caracter C separate printr-un singur spatiu. Daca A este 0 (zero) atunci caracterul C este inserat la inceputul secventei; daca A este 1 (unu) atunci caracterul C este inserat la sfarsitul secventei.

Date de iesire

Fisierul de iesire secvreg.out contine N linii. Pe cea de a i-a linie va fi afisata lungimea celei mai scurte subsecvente regulate (formata din caractere consecutive ale secventei) care contine paranteza inserata la pasul i. Daca nu exista o astfel de subsecventa, pe linia respectiva veti afisa 0.

Restrictii

Lungimea secventei initiale de paranteze <=100 000
1<=N<=100 000

Exemple

secvreg.in secvreg.out secvreg.in secvreg.out secvreg.in secvreg.out

(
1
1 )

2 (]
3
1 )
0 )
0 (
0
0
2
[])
3
0 )
0 (
0 (

0
2
6

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2004: cifre1, super, apm, bile1, factk, schimb, caini, descfib, maraton, masina1, otilia, multiplu, tub, pasune, remi, m01, robot1, na, sir23, paralel, zaruri, bomboane, dotnet, divizor, tren1, joc5, tvshow, pachete, soldati1, echipe, omizi, suma1, aedaro, concurs1, windows, comb, renju, latime, vectori, ghici, subperm, puncte, mere1, spirala, distanta, piloti
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre deque: platforma, compus, copaci, sirag, leaves, cover, drept1, stalpi1, gropi1
Software recomandat
surse trimise | ajutor