Hercule 2 : l'Hydre de Lerne

Histoire

Pour son deuxième travail, Eurysthée demanda à Hercule de tuer l'Hydre, une sorte de dragon possédant plusieurs têtes et qui hantait les marais de Lerne.

Pour mener à bien sa mission, Hercule, muni de sa seule épée décida de trancher les têtes de l'Hydre.

Afin de ménager sa forme et d'éviter tout claquage musculaire, Hercule était contraint, à chaque coup d'épée, de varier assez peu la force du coup par rapport au coup précédent. D'un autre côté, il aimait varier ses coups. Ainsi, à chaque nouveau coup donné, Hercule pouvait couper soit une tête de plus, soit une tête de moins qu'au coup précédent...

De plus, Hercule connaissait une propriété étonnante de l'Hydre. Si, après une coupe, celle-ci se retrouvait avec un nombre de têtes à la fois premier et impair, alors 13 têtes supplémentaires repoussaient instantanément.

Le nombre de têtes de l'Hydre est indiqué en entrée du défi. Combien de têtes Hercule doit-il couper à chaque coup pour donner le moins de coups possibles ? Attention, le dernier coup d'épée d'Hercule doit suivre aussi les règles énoncées plus haut et couper exactement le nombre de têtes restantes.

Testez votre code

Si l'Hydre avait eu 6 têtes, alors une des meilleures stratégies pour Hercule aurait été de couper ce nombre de têtes : 1, 2, 3, 4, 5, 4, 5, 6, 7, 8.
Ce problème est tiré de c0d1ng UP 2015

Type de retour

une séquence de nombres entiers

Entrée du problème

61

Formulaire de réponse

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

Tags : cup15 combinatoire récursivité