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

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


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

Gigel este un pasionat excursionist. Îi plac în special excursiile la munte. La sfârşitul acestei săptămâni el şi-a propus să traverseze un munte din apropierea oraşului Cluj. Atâta doar că echipa Salvamont locală i-a impus nişte condiţii:
– lungimea drumului trebuie să fie exact 2n-2 metri, valoarea n fiind dată de salvamontişti;
– trebuie să plece de la poalele muntelui şi trebuie să ajungă tot la poalele muntelui de partea cealaltă la aceeaşi altitudine;
– nu are voie să coboare sub altitudinea de plecare;
– poate traversa drumul doar folosind trei tipuri de paşi:
1) pas pe orizontală de lungime 2, deci de tipul (2, 0)
2) pas „în sus” de lungime 1, deci de tipul (1, 1)
3) pas „în jos” de lungime 1, deci de tipul (1, -1)
– drumul lui nu are voie să aibă „vârf” la altitudinea 1, adică nu are voie ca fiind la un moment dat, pe parcursul drumului, la altitudinea de plecare, să facă un pas în sus urmat imediat de un pas în jos.

Cerinţă

Dată fiind valoarea n să se determine în câte moduri poate Gigel să traverseze muntele respectând condiţiile echipei Salvamont.

Date de intrare

Fişierul de intrare munte.in conţine o singură linie pe care se află numărul natural n.

Date de ieşire

Fişierul de ieşire munte.out va conţine o singură linie pe care va fi scris numărul de modalităţi în care Gigel poate realiza traversarea muntelui.

Restricţii

1 ≤ n ≤ 100
Pentru 60% din teste rezultatul este un întreg pe 64 de biţi.

Exemple

munte1.inmunte1.outExplicaţii
1 1 Lungimea drumului fiind 2*1-2=0, există o singură modalitate de a traversa muntele (aceea de a sta pe loc)
2 1 Lungimea drumului fiind 2*2-2=2, există o singură modalitate de a traversa muntele, printr-un pas de lungime 2.



Varianta din dreapta nu este corectă deoarece nu respectă ultima condiţie.
3 3 Cele 3 modalităţi corecte de a traversa muntele cu un drum de lungime 4 sunt:



Orice alt mod de a traversa muntele pe un drum de lungime 4 este incorect.

autor: Prof. Marinel Şerban
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2007: ceas, numere4, cifru, oua, turn, div3, jeton, politic, trecere, agitatie, lacuri, secv, sotron, triunghi, apel, castel, excursia, matricea, randuri, zidar, desc, felinar, joc6, log, maxq, tric, cover, dist, promo, puncte1, role
De acelaşi autor: premii, finala, fractii, trei, manevre, nrcuv, an, vopsea, opmat, tramvai, bipal, kpal, sarpe, replace, factori, barca, perechi, grupe, cod, reactii, factura, decript, trenuri, holo, cifre, firma, tribile, mesaj, tricouri, pajura, monede, programs, fry, repeat, red, pavaj, bacan, nrbinar, invest, cutie2, loc, depou, nr3, zid, felinare, sir3, sqr, carte, labirint, stea, count, evaluare, super, schimb, zaruri, vectori, spirala, desen1, rima, ceas1, romane, sms, bac, excursia, joc7, furnici, cezar, marcare, excursie1, culmi, sume1, schi, nr4, fractie, cod3, medii, tren3, top, sant1, imagine, ocr, perfect, pluton, reforma, alee, ceas2, paritate, borcane, aranjare, comoara1, culmi1, reactivi, submult, sablon1, sir8, sume2, dansatori, smith, tom, matriosca, asociativ, control1, calorii, immortal, concat, mat, cubinvers, mine, divizori, cheie, stelar, joct, minmax, cladire, adunscad, razboi, ore, oras1, sumprod, prisme, operatii1, lgdrum, unupatru, chibrituri, extraprime, prieten, rebus1, grindina, opmult, betisoare, antitero, clase, pagini, ornament, ordine, spioni1
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, expresii, arbnr, cod1, munte, shgraf, desc, lex, 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 numere mari: fib, 2sir, test, sort, gray, siruri, vecini, div, sir2, nrcuv2, scor, hanoig, red, matrice3, pavaj, depou, pm, sqr, set, albine, teatru1, descfib, tub, m01, soldati1, euclid, mutare, bifo, banda10, sg1, cutii, zumzi, numere7, trapez, patrate6, muguri, impozit, kbiti, m4, numar3, parbit, petrecere, randomizare, radical, ghinion, aliniere, sumb, cavaleri, camera616, numar4, pavari, asfalt, rotund, cos, risipa, xpn, dale, codpatrat, culori1, plus, minm, pomi, cifrab, subsets, doitrei, conjectura, ech, inventie
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, maxq, cover, dist, 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