Jucându-se cu monede de aceeaşi dimensiune, Gigel „construieşte” grămezi de monede care „stau” unele peste altele, astfel încât, cu excepţia monedelor de la baza grămezii, care stau lipite una de alta, monedele de pe rândurile superioare sunt lipite una de alta şi se sprijină pe câte două monede alăturate de pe rândul inferior.
Astfel, construcţia din stânga este corectă deoarece moneda din rândul superior se sprijină pe două dintre monedele alăturate din rândul de la baza construcţiei, în timp ce construcţia din dreapta nu este corectă, deoarece moneda din rândul superior nu se sprijină pe nimic, şi, în plus, ultima monedă din rândul de la baza construcţiei nu este lipită de cea din stânga ei. Aşa cum îl ştim, curios din fire, Gigel îşi pune întrebarea „câte astfel de aranjări corecte de monede care să aibă baza formată din n monede, există”?
Cerinţă
Dat n, determinaţi numărul de construcţii corecte cu n monede la bază care pot fi realizate.
Date de intrare
Fişierul de intrare monede.in conţine pe prima linie un număr natural n, reprezentând numărul de monede aflat la baza unei construcţii corecte.
Date de ieşire
Fişierul de ieşire monede.out conţine pe prima linie un număr natural reprezentând numărul de construcţii corecte care pot fi realizate.
