ultima problemă
grupă: micăsursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
Timp maxim de execuţie / test:
Memorie totala disponibilă / stivă:
Să considerăm o stivă, iniţial vidă. Putem efectua următoarele operaţii:
push(X) - se introduce în stivă litera
X (evident, în vârful stivei);
pop - se extrage litera aflată la vârful stivei (operaţia
pop se execută atunci când stiva este nevidă);
top - se afişează litera aflată la vârful stivei (operaţia
top se execută atunci când stiva este nevidă).
O secvenţă de operaţii este considerată corectă dacă:
- iniţial stiva este vidă;
- se execută o serie de operaţii
push, pop, top, fără a executa
pop sau
top când stiva este vidă;
- la final stiva este vidă.
Utilizând secvenţe corecte de operaţii, putem afişa diferite şiruri de caractere.
De exemplu, şirul
ABCACBA poate fi generat astfel:
push(A),top,pop,push(B),top,pop,push(C), top, pop etc.
O altă secvenţă de operaţii corectă, dar mai scurtă ar fi:
push(A),top,push(B),top,push(C), top,push(A),top,pop,top,pop,top,pop,top,pop.
Cerinţă
Dat fiind un şir format din litere mari, să se determine numărul minim de operaţii dintr-o secvenţă corecte care afişează şirul dat.
Date de intrare
Fişierul de intrare
stiva.in conţine pe prima linie un şir format numai din litere mari.
Date de ieşire
Fişierul de ieşire
stiva.out va conţine o singură linie pe care va fi scris numărul minim de operaţii dintr-o secvenţă corecte care afişează şirul din fişierul de intrare.
Restricţii
Lungimea şirului este ≤ 500.
Exemple
stiva.instiva.out15
Articole recomandate
Probleme recomandate
De la ONI 2008 : ab2 , iepuras , palind , auto , div , teatru , pm , submat , reteta2 , rezervatie , creioane , melci , mere2 , felinare , joc3 , 2numere , fi , tablou , borcane , mexc , tcast , dep , dist1 , banda , pavare , poarta , aranjare , bile4 , subgeom , albinuta1 , curent , pviz , atac2 , virus 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 , 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 , 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 stiva : sl , teren , reactii , complex , auto , bile3 , chimie2 , vile , puncte1 , masina3 , matrice1 , dir , munte2 , perle , basm , predecesor , expresie1 , telecab , expresie2 , liste , intervale , jocs , expeval , copaci2 , plus , azeval , unific , swap , stiva1 , ecp , charlie Despre programare dinamică : vedete , fbr , tgv , zeratul , rv , comun , retea , circuit , sumdif , copaci , drum , text , palind , joc , vikingi , rafturi , balaur , plimbare , party , pc , pioni , seif , iepuri , numere3 , perm , ture , bilete , prop , ro , reduceri , cuburi , invest , cutie2 , stalpi , nr2 , judete , strict , auto2 , tree , jobs , leaves , pstring , program , datorii , senzori , farfurii , joc1 , barbie , ambigram , rlcs , cub1 , bio , chimie1 , otilia , pasune , remi , sir23 , tren1 , joc5 , pachete , echipe , comb , agitatie , ivv , peste , pitici , pipe , shgraf , tabara1 , stop , randuri , zidar , log , sant , produs , subsir , cover , bcast , emax , dist , mesaj1 , imax , avere , asmax , raft , suma2 , joc12 , fni , nr4 , join , transport , masina3 , lsort , microvirus , fat , cafea , echipe1 , anticip , bsir , diamant , petrom , evantai , spion , acolor , evo , bombo , lacusta , lant , team , pitici1 , numere8 , dep , subgeom , pviz , tir1 , cabane , piramida1 , mosia , cuvinte1 , gaina , materom , sortari , turnuri , trans , politie , codul , dansatori , nkbiti , kperms , treegame , siruri2 , 123 , jucarii , bradut , joc15 , expozitie , text3 , ic , echilibru , distsir , kmax , stalpi1 , gaz , triunghi2 , v2d , cuiburi , mine , orientare , activ , secvbiti , kcons , pokemon , ubergraf , left , acerc , autostrazi , kdist , select , cazare , fluviu , telecomanda , parcela , pion , subs , suma4 , sirmax , bdotcom , viena , sablon2 , telecab , ikebana , radare , hacker , obstacole , robotel , centrala , verigi , cds , wg , minusk , radioactiv , enigma , jb , efect , maxviz , ripstick , progresii , maxtri , combcuv , blis , subsiruri , mijloc , probleme , unuzero , palindrom1 , minerale , speed , zmax , spider , cntgcd , interclasare , bus , pariuri , riglef , fractii2 , fall , arbsum , conuri , arbvalmax , procente , metrou
Software recomandat