Colegii de clasă
a lui Gigel s-au hotărât să participe la o activitate sportiva, activitate la
care poate participa doar o singura grupa de elevi din clasă.
Pentru a construi grupa, elevii din clasa lui Gigel au fost numerotati, în ordinea
din catalog, de la 1 la n.
Grupa ce trebuie
formata trebuie să îndeplinească o singura condiţie: nu este permis ca doi elevi
care apar în catalog unul după altul să facă parte din aceeaşi grupă.
Cerinţă
Dat fiind n, numărul de elevi
din clasa lui Gigel, să se determine in câte moduri se poate forma grupa.
Date de intrare
Fişierul de intrare grupe.in
conţine pe prima linie un număr natural nenul n,
reprezentând numărul de elevi din clasa lui Gigel.
Date de ieşire
Fişierul de intrare grupe.out
conţine pe prima linie un număr natural, reprezentând numărul de modalitati
in care se poate constitui grupa respectând condiţiile impuse.
Restricţii şi
precizări
1 <= n <= 90
Grupa trebuie să contina cel puţin un elev.
Exemplu
grupe.in
grupe.out
Explicaţii
5
12
Grupele
care se pot forma sunt:
{1},{2},{3},{4},{5},{1,3},{1,4},{1,5},{2,4},{2,5},{3,5},{1,3,5}