Fişierul intrare/ieşire:recurenta.in, recurenta.outSursăAlgoritmiada 2009, Runda 3
AutorStefan Alexandru FilipAdăugată deProstuStefan-Alexandru Filip Prostu
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Recurenta

Dubota a invatat la scoala despre numerele Fibonacci. Aceste numere sunt definite in felul urmator: primii termeni ai sirului sunt 0, F0 = F1 = 1, iar al n-lea termen, 2 ≤ n, se obtine adunand termenii n-1 si n-2 ai sirului Fn = Fn-1 + Fn-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. D0 = D1 = ... = Dk-1 = 1, Dn = Dn-1 + Dn-2 + ... + Dn-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.

Date de intrare

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

Date de ieşire

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

Restricţii

  • k ≤ n ≤ 10000
  • 2 ≤ k ≤ 1000

Exemplu

recurenta.inrecurenta.out
6 3
17

Explicaţie

D0 = D1 = D2 = 1, D3 = 3, D4 = 5, D5 = 9, D6 = 17.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content