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

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


Timp maxim de execuţie/test:
0.1 secunde
Memorie totala disponibilă/stivă:
16 MB/1 MB

Numim SCP (secventã corect parantezatã) o secventã formatã din paranteze rotunde deschise si închise care poate fi formatã aplicând urmãtoarele reguli:
1. Sirul vid este SCP
2. Dacã S este SCP atunci (S) este de asemenea SCP
3. Dacã A si B sunt SCP, atunci AB este SCP.
Sã considerãm un sir constituit din paranteze rotunde si pãtrate (deschise si închise). Asupra acestui sir putem aplica urmãtoarele operatii:
1. orice parantezã pãtratã deschisã poate fi înlocuitã cu 0, 1, 2 sau mai multe paranteze rotunde deschise.
2. orice parantezã pãtratã închisã poate fi înlocuitã cu 0, 1, 2 sau mai multe paranteze rotunde închise.
Observati cã este permisã înlocuirea unei paranteze pãtrate cu 0 paranteze rotunde (adicã este permisã stergerea ei).

Cerinţă

Dat fiind un sir format din paranteze pãtrate si rotunde, scrieti un program care sã determine o secventã corect parantezatã de lungime minimã ce se poate obtine din sirul dat aplicând operatiile descrise în enunt.

Date de intrare

Fisierul de intrare scp.in contine pe prima linie un sir format din paranteze rotunde si pãtrate.

Date de ieşire

Fisierul de iesire scp.out va contine o singura linie pe care va fi scrisã o secventã corect parantezatã de lungime minimã ce se poate obtine din sirul dat aplicând operatiile descrise în enunt. Dacã problema nu are solutie, veti afisa pe prima linie cuvântul IMPOSIBIL.

Restricţii

  • 0<Lungimea sirului dat<=2000
  • Dacã existã mai multe solutii de lungime minimã, afisati pe oricare dintre acestea.

Exemple

scp.in scp.out Explicaţii
[)())(]()] (()())()() Prima parantezã pãtratã deschisã este înlocuitã de douã paranteze rotunde deschise.
Prima parantezã pãtratã închisã este înlocuitã de o parantezã rotundã deschisã.
A doua parantezã pãtratã închisã este înlocuitã de 0 paranteze rotunde deschise (adicã este stearsã).

prof. Emanuela Cerchez
Liceul de Informatică „Grigore Moisil” Iaşi
emanuela.cerchez@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2008: celule, premii, cai, forum, vedete, film, finala, ab, nice, supertri, mod3, degrade, fractii, balanta, inginer, camp, ozn, hora, trei, rebus, sl, detinut, fbr, noroc, simetric, egal, manevre, connect3, gropi, nrcuv, ruleta, carti, pod, bonuri, tgv, fib, uscat, 2sir, atac, matrice2, zeratul, afise, an, dezbateri, test, miniasm, platforma, lac, vopsea, harta, nrbun2, barfa, nrbun, bunici, opmat, acop, tren, cub, picnic, cursa, rv, compus, comun, magic, votare, onu, tramvai, bipal, nspecial, retea, secvop
De acelaşi autor: celule, 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, secvreg, 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 şiruri de caractere: ab, sl, nrcuv, rv, kpal, chimie, reteta, replace, grad, index, cod, text, decript, spam, complex, cifre, anagrame, balbe, criptmat, mesaj, maxim, astre, sablon, formule, ed, balls, vocale, prop, bacan, novel, bitslang, text2, ref, scor2, convert, cod2, compress, pstring, sub, rima, program1, sms, circular, randuri, cezar, bifo, joc9, pal, bare, joc12, fractie, cod3, tunel, csir, top, ratina, cifru1, limbaj, adun, ecuatii, dir, paritate, virus, sir6, mesaj2, text1, sirul, ogorul, rez, sablon1, anag, sir8, seti, secvsir, dp, cuvant, strings, antipatie, fractie1, links, ordonare, text3, concat, codif, cheie, alfabetar, cuvinte2, comp, litere, mxl, mesaj3, expresie2, grad2, antic, zuma, expeval, combcuv, lgdrum, subtitrare, compresie, zigzag, azeval, fraze, subsecvente, showroom, rebus1, agenda, opmult, betisoare, reziston, clase, vot2, ecp, smiley, charlie, cript, scadere, spioni1, sablon3, expand, culori3, virgule
Software recomandat
Chestionare recomandate
surse trimise | ajutor