Fişierul intrare/ieşire:piramida.in, piramida.outSursăLot 2005 Sibiu
AutorRodica PinteaAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Piramida

O piramida de inaltime N are la baza (baza fiind considerata de nivel 1) N numere naturale nenule. Pe nivelul urmator al piramidei (nivelul 2) exista N-1 numere, fiecare numar de pe nivelul 2 fiind obtinut cu formula P2,i = P1,i + P1,i+1, pentru i = 1, .. , N-1, si asa mai departe. Astfel, pe nivelul K sunt N-K+1 numere, fiecare numar de pe acest nivel fiind obtinut cu formula Pk,i = Pk-1,i + Pk-1,i+1 pentru i = 1, .. , N-K+1.

Piramida este S-generatoare daca numarul de pe ultimul nivel este S.

Cerinta

Pentru o valoare S data, se cere sa se determine cate piramide S-generatoare de inaltime maxima exista.
De exemplu, pentru S = 10, exista 3 astfel de piramide:

Piramidele de mai jos sunt 10-generatoare, dar nu au inaltime maxima:

Date de intrare

In fisierul piramida.in se afla un singur numar natural reprezentand valoarea lui S.

Date de iesire

Fisierul de iesire piramida.out va contine o singura linie pe care va fi scris un singur numar natural reprezentand numarul total de piramide S generatoare de inaltime maxima modulo 10000.

Restrictii

  • 1 ≤ S ≤ 600000

Exemplu

piramida.inpiramida.out
1
1
3
2
10
3
20
7
101
714
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content