Neutralisation de Kryptonite

Connaissant les faiblesses de Superman (la Kryptonite et la combinatoire), Lex Luthor lui soumet le maléfique problème suivant.

Devant lui, Superman dispose d'une sorte de plateau allongé contenant plusieurs emplacements alignés. Le nombre réel d'emplacements est donné en entrée du problème. Supposons pour l'exemple qu'il y en ait 6 :

Superman dispose d'un autre côté de plusieurs pierres de kryptonite verte et d'antikryptonite orange (il en a autant qu'il veut). Il doit disposer une pierre dans chaque emplacement. Par exemple :

Mais il y a une contrainte supplémentaire : pour ne pas être affaibli par la kryptonite, il faut nécessairement que la configuration orange, vert, orange, vert, orange, formée de 5 pierres, soit présente quelque part dans l'agencement qu'il propose.

Par exemple, avec 6 emplacements, il n'y a que 4 façons de resoudre le problème :

Pour le nombre d'emplacements indiqué en entrée, combien de configurations différentes permettent à Superman de respecter ces contraintes ?

Exemple

Si le nombre d'emplacements est 7, alors il y a 11 façons différentes de disposer les pierres.

Ce problème est tiré de c0d1ng UP 2016

Type de retour

un nombre entier

Entrée du problème

23

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : cup16 combinatoire