| Fişierul intrare/ieşire: | piramida.in, piramida.out | Sursă | Lot 2005 Sibiu |
| Autor | Rodica Pintea | Adăugată de |  Pripoae Teodor Anton •toni2007 |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | piramida.out |
|---|---|
| 1 | 1 |
| 3 | 2 |
| 10 | 3 |
| 20 | 7 |
| 101 | 714 |
