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

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


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

Fie X multimea definita dupa urmatoarele reguli:
· sirul vid apartine multimii X
· daca A si B apartin multimii X, atunci atat sirul (A) cat si AB apartin multimii X.

Elementele multimii X sunt denumite expresii corect parantezate.
De exemplu, urmatoarele siruri sunt expresii corect parantezate:
()(())()
(()(()))

Urmatoarele expresii nu sunt corect parantezate:
(()))(()
())(()

Fie E o expresie corect parantezata. Lungimea expresiei E este egala cu numarul de paranteze din aceasta expresie. Adancimea expresiei E (notata D(E)) este definita dupa cum urmeaza:

D(E)=0, daca E este vida
D(E)=D(A)+1, daca E = (A), si A este din X
D(E)=max(D(A),D(B)), daca E = AB, si A, B sunt din X

Cerinta

Scrieti un program care sa determine numarul de expresii corect parantezate de lungime n si adancime d.

Date de intrare

Fisierul de intrare expresii.in contine o singura linie pe care se afla doua numere naturale n d, separate printr-un spatiu, avand semnificatia din enunt.

Date de iesire

Fisierul de iesire expresii.out va contine un singur numar natural reprezentand numarul de expresii corect parantezate de lungime n si adancime d.

Restrictii

  • 1<n<39
  • 0<d<20

Exemple

expresii.in expresii.out Explicatie

6 2

3

Cele 3 expresii corect parantezate de lungime 6 si adancime 2 sunt:
(())()
()(())
(()())

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
Despre combinatorică: manevre, carti, bonuri, test, cub, nspecial, circuit, numere, cs, pluricex, parent, gray, siruri, anagrame, party, net, scaune, sir, monede, aztec, nrcuv2, perm, race, hanoig, red, grup, hperm, depou, grazing, pm, reteta2, playlist, young, pizza1, albine, caramele, teatru1, tub, robot1, sir23, soldati1, concurs1, comb, arbnr, cod1, munte, shgraf, desc, lex, munte1, maxperm, role, avere, vizibil, prime1, hexa, patrat, carti2, puncte2, pact, aranjari, numere5, borg, acolor, sg1, perfect, cifru2, bile4, pviz, culmi1, piramida1, trapez, frunze, sir7, logic, coduri, jetoane, kperms, tablite, secvpar, lego, permutari, binperm, multiplu1, operatii, fotbal, kbiti, jucarii, bradut, expozitie, parbit, kmax, petrecere, tango, rege, cd1, cifru3, kcons, bubblesort, hawaii, randomizare, kdist, reuniune, echipa, ghinion, cavaleri, camera616, covor, subm, grupuri, pavari, asfalt, adunscad, rotund, sport2, arbore1, lant1, module, nrperm, oneton, nrpomi, cover1, nrpal, probleme, optim, poly, vot1, sudoku1, flori2, xnumere, showroom, cntgcd, subsets, nkd, nrgraf, spion1, puteri, stiva1, permtr, relatii, 2sah, matcnt, magic7, nmult, roua
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, agitatie, aparitii, apel, randuri, zidar, log, maxq, cover, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, 2ndesc, flori2, cntgcd, 2sah, matcnt, nmult
surse trimise | ajutor