Fişierul intrare/ieşire:flori4.in, flori4.outSursăONI 2013, clasa a 10-a
AutorVlad GeorgieAdăugată descipianusFMI Ciprian Olariu scipianus
Timp execuţie pe test1 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Flori 4

Lalelele din Parcul Soarelui au fost numerotate de la 1 la n. Se doreşte formarea unui buchet, care să conţină cel puţin o floare, iar două flori numerotate consecutiv să nu aparţină buchetului.

Cerinţă

Fiind dat n, numărul de flori, să se determine în câte moduri se poate forma buchetul.

Date de intrare

Fişierul de intrare flori4.in conţine pe prima linie un număr natural n, reprezentând numărul de flori.

Date de ieşire

În fişierul de ieşire flori4.out conţine pe prima linie un număr natural ce reprezintă numărul de buchete modulo 9001.

Restricţii

  • 1 ≤ n ≤ 10000;
  • Pentru 30% din teste n este mai mic sau egal decât 26;
  • Pentru 60% din teste n este mai mic sau egal decât 1000.

Exemplu

flori4.inflori4.out
5
12
7
33

Explicaţie

Primul exemplu : {1}, {2}, {3}, {4}, {5}, {1,3}, {1,4}, {1,5}, {1,3,5}, {2,4}, {2,5}, {3,5}
Al doilea exemplu : {1}, {2}, {3}, {4}, {5}, {6}, {7}, {1,3}, {1,4}, {1,5}, {1,6}, {1,7}, {1,3,5}, {1,3,6}, {1,3,7}, {1,4,6}, {1,4,7}, {1,5,7}, {1,3,5,7}, {2,4}, {2,5}, {2,6}, {2,7}, {2,4,6}, {2,4,7}, {2,5,7}, {3,5}, {3,6}, {3,7}, {3,5,7}, {4,6}, {4,7}, {5,7}

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content