== include(page="template/taskheader" task_id="piramida") ==
Poveste si cerinta...
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 $P{~2,i~}$ = $P{~1,i~}$ + $P{~1,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 $P{~k,i~}$ = $P{~k-1,i~}$ + $P{~k-1,i+1~}$ pentru $i$ = $1$, .. , $N-K+1$.
Piramida este $S-generatoare$ daca numarul de pe ultimul nivel este $S$.
h2. 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:
!problema/piramida?pir1.jpg!
Piramidele de mai jos sunt $10-generatoare$, dar nu au inaltime maxima:
!problema/piramida?pir2.jpg!
h2. Date de intrare
Fisierul de intrare $piramida.in$ ...
In fisierul $piramida.in$ se afla un singur numar natural reprezentand valoarea lui $S$.
h2. Date de iesire
In fisierul de iesire $piramida.out$ ...
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$.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ S ≤ 600000$
h2. Exemplu
table(example). |_. piramida.in |_. piramida.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
| 1
|
| 3
| 2
|
| 10
| 3
|
| 20
| 7
|
| 101
| 714
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="piramida") ==
