Fişierul intrare/ieşire:munte3.in, munte3.outSursăBaraj ONI 2007
AutorMarinel SerbanAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Munte3

Gigel este un pasionat excursionist. Ii plac in special excursiile la munte. La sfarsitul acestei saptamani el si-a propus sa traverseze un munte din apropierea orasului Cluj. Atata doar ca echipa Salvamont locala i-a impus niste conditii:

  • lungimea drumului trebuie sa fie exact 2n-2 metri, valoarea n fiind data de salvamontisti;
    trebuie sa plece de la poalele muntelui si trebuie sa ajunga tot la poalele muntelui de partea cealalta la aceeasi altitudine;
  • nu are voie sa coboare sub altitudinea de plecare;
  • poate traversa drumul doar folosind trei tipuri de pasi:
    • pas pe orizontala de lungime 2, deci de tipul (2, 0)
    • pas "in sus" de lungime 1, deci de tipul (1, 1)
    • pas "in jos" de lungime 1, deci de tipul (1, -1)
  • drumul lui nu are voie sa aiba "varf" la altitudinea 1, adica nu are voie ca fiind la un moment dat, pe parcursul drumului, la altitudinea de plecare, sa faca un pas in sus urmat imediat de un pas in jos.

Cerinta

Data fiind valoarea n sa se determine in cate moduri poate Gigel sa traverseze muntele respectand conditiile echipei Salvamont.

Date de intrare

Fisierul de intrare munte3.in contine o singura linie pe care se afla numarul natural n.

Date de iesire

Fisierul de iesire munte3.out va contine o singura linie pe care va fi scris numarul de modalitati in care Gigel poate realiza traversarea muntelui.

Restrictii

  • 1 ≤ n ≤ 100
  • Pentru 60% din teste rezultatul este un intreg pe 64 de biti.

Exemplu

munte3.inmunte3.out
1
1
2
1
3
3

Explicatie

  1. Lungimea drumului fiind 2*1-2=0, exista o singura modalitate de a traversa muntele (aceea de a sta pe loc)
  2. Lungimea drumului fiind 2*2-2=2, exista o singura modalitate de a traversa muntele, printr-un pas de lungime 2.

    Varianta din dreapta nu este corecta deoarece nu respecta ultima conditie
  3. Cele 3 modalitati 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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content