Vélociraptors – Épreuve régionale 2016

Niveau 1

Énoncé

Le vélociraptor est un petit dinosaure aussi agile que féroce. Un jeune vélociraptor atteint sa maturité au bout d'un an seulement.

Les vélociraptors naissent et vivent en couple. À l'âge d'un an, chaque couple donne naissance à deux couples. À l'âge de deux ans, chaque couple donne naissance à un couple. Les vélociraptors meurent à l'âge de 3 ans.

Étant donné une population initiale de vélociraptors, déduisez-en la population totale après n années.

Entrée

  • La première ligne est un couple d'entiers j et v séparés par une espace, le nombre initial de couples de vélociraptors âgés d'un an et de deux ans.
  • La seconde ligne est un entier n, le nombre d'années passées après la génération initiale.

Sortie

Un unique nombre entier, le nombre total w de couples de vélociraptors.

Contraintes

  • 0 ≤ j ≤ 1 000
  • 0 ≤ v ≤ 1 000
  • 0 ≤ n ≤ 22
  • w ≤ 2 000 000 000

Contraintes d'exécution

Utilisation mémoire maximum
100 kilo-octets
Temps d'exécution maximum
100 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
1 1
4
Exemple de sortie
58
Commentaire

Voici le détail de chaque génération :

  • Initiale : 1 couple âgé d'un an et 1 couple âgé de deux ans.
  • Première génération : 3 couples âgés d'un an et 1 couple âgé de deux ans.
  • Deuxième génération : 7 couples âgés d'un an et 3 couples âgés de deux ans.
  • Troisième génération : 17 couples âgés d'un an et 7 couples âgés de deux ans.
  • Dernière génération : 41 couples âgés d'un an et 17 couples âgés de deux ans.

Il y a donc 58 couples de vélociraptors au bout de quatre années.