Fibonacci et compagnie – Qualification 2006

Level 3

ENONCE

La suite de Fibonacci est définie par :

u(0) = 1

u(1) = 1

u(n) = u(n-1) + u(n-2)

On souhaite généraliser cette suite.

M étant donné, on pose :

u(n) = 1 si n \< m,

u(n) = u(n-1) + u(n-m) sinon

Ainsi, on retrouve la suite de Fibonacci en utilisant m = 2. Vous devez écrire une fonction qui prend en arguments n et m et qui renvoie u(n).

Exemple avec m = 3 :

u(30) = u(29) + u(27) = ... = 58425

CONTRAINTES

  • n \<= 5000, m \< n
  • u(n) \< 1000000000

ENTREE

  • La première ligne de l'entrée contient deux entiers : n et m, séparés par une espace.

SORTIE

La sortie contient une unique ligne : l'entier retourné par votre fonction.

Runtime constraints

Maximum memory usage
2000 kilobytes
Maximum execution time
250 milliseconds

Input/output samples

Sample input
30 3
Sample output
58425

Submit your solution

You have to register or log in to be able to submit your solution.