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

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


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

Nafets lucreaza la un algoritm. Din pacate, entuziasmat de problema pe care o rezolva, uita cateodata sa inchida parantezele care determina structura de bloc a pseudocodului. Ca atare algoritmul lui poate arata in felul urmator: 
 (() 

 In acest caz, Nafets a uitat sa inchida o paranteza. In functie de momentul in care a sarit respectiva paranteza, algoritmul ar fi putut fi (()) sau ()().

Cerinta 

Scrieti un program care citeste un sir de paranteze rotunde reprezentand algoritmul facut de Nafets. Programul vostru trebuie sa calculeze numarul de algoritmi (siruri de paranteze corect inchise) la care s-ar fi putut gandi Nafets, stiind ca el nu face nici o alta greseala decat sa uite cateodata paranteze inchise. 

Date de intrare 

Pe prima linie a fisierului de intrare program.in se gaseste sirul de paranteze corespunzator algoritmului scris de Nafets.

Date de iesire 

Daca X este numarul de algoritmi posibili, pe prima linie a fisierul de iesire program.out afisati restul impartirii lui X la 9731.

Restrictii

  • 1 <= numarul de paranteze (deschise + inchise) din fisierul de intrare <= 400
  • Sirul de paranteze din fisierul de intrare este obtinut exact in modul descris in descrierea problemei 

Exemplu

program.in 

program.out 

(() 

Stefan Ciobaca
Universitat Konstanz
stefan.ciobaca+gmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
De acelaşi autor: Curs algebra
Probleme recomandate
De la .campion 2005: cuc, prime, radio, text2, honest, police, comori, patrate3, fisc, ref, pcod, zmeu, loc, nr01, scor2, judete, strict, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, jobs, leaves, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, carte, set, barbie, labirint, firma1, vile, game, donald, ambigram, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, jokes, pizza1, albine, lot, atac1, monede1, count, exam, herbert, sudoku, bio, metro
De acelaşi autor: parent, dotnet, comb, subperm, newcomp, tric, cladiri, bsir, logic
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, 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, stiva, 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
surse trimise | ajutor