recurenta

Recurenta

== include(page="template/taskheader" task_id="recurenta") ==

Poveste şi cerinţă...

Dubota a invatat la scoala despre numerele Fibonacci. Aceste numere sunt definite in felul urmator: primii termeni ai sirului sunt $0$, $F{~0~} = F{~1~} = 1$, iar al n-lea termen, $2 ≤ n$, se obtine adunand termenii $n-1$ si $n-2$ ai sirului $F{~n~} = F{~n-1~} + F{~n-2~}$. Acum Dubota este curios care sunt termenii sirurilor ai caror termeni se obtin adunand ultimii $k$ termeni si au primii $k$ termeni egali cu $1$. $D{~0~} = D{~1~} = ... = D{~k-1~} = 1, D{~n~} = D{~n-1~} + D{~n-2~} + ... + D{~n-k~}, k ≤ n$. Fiind dat $k$, Dubota va cere sa ii spuneti care este termenul de indice $n$ al sirului care se formeaza prin regula prezentata mai sus.

h2. Date de intrare

Fişierul de intrare $recurenta.in$ ...

Fişierul de intrare $recurenta.in$ va contine doua numere separate prin spatiu, $n$ si $k$ cu semnificatia din enunt.

h2. Date de ieşire

În fişierul de ieşire $recurenta.out$ ...

În fişierul de ieşire $recurenta.out$ va contine un singur numar, termenul de indice $n$ al sirului.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $k ≤ n ≤ 10000$
* $2 ≤ k ≤ 1000$

h2. Exemplu
table(example). |_. recurenta.in |_. recurenta.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 3
| 17

|
h3. Explicaţie

...

D{~0~} = D{~1~} = D{~2~} = 1, D{~3~} = 3, D{~4~} = 5, D{~5~} = 9, D{~6~} = 17.

== include(page="template/taskfooter" task_id="recurenta") ==

3654