Le coffre à interrupteurs

Une fois de plus, vous allez devoir ouvrir un coffre... Mais ce ne sera pas facile. Le code d'ouverture est en effet masqué dans un système d'interrupteurs qu'il va falloir comprendre, afin d'obtenir la combinaison du coffre. Le système se présente sous la forme de 12 interrupteurs, initialement éteints. Une série bien précise d'action sur ces interrupteurs permet de les allumer tous. Les contraintes sont les suivantes. À chaque instant, il n'y a que deux interrupteurs au mieux qui peuvent être actionnés :

  • le plus à gauche (on peut l'éteindre ou l'allumer)
  • celui sité juste à droite du premier interrupteur allumé (on peut aussi l'éteindre ou l'allumer).

Supposons par exemple que nous ayons atteint cette configuration :

Nous avons deux possibilités :
Actionner le premier interrupteur :

*ou bien* actionner l'interrupteur juste à droite du premier interrupteur allumé :

Voici un autre exemple. Supposons que nous ayons atteint cette configuration :

Nous avons encore deux possibilités :
Actionner le premier interrupteur :

Actionner l'interrupteur juste à droite du premier interrupeur allumé :

Au départ, tous les interrupteurs sont éteints :

La seule action possible est d'actionner le premier interupteur. Il y a une seule façon de manipuler les interrupteurs pour parvenir à la position où ils sont tous allumés, tout en minimisant le nombre de manipulations.

Notons à présent qu'à une configuration d'interrupteurs correspond un nombre, si on écrit 0 pour un interrupteur éteint et 1 pour un interrupteur allumé, alors on peut faire correspondre l'écriture binaire d'un nombre à une configuration d'interrupteurs. Par exemple, la configuration suivante :

correspond à l'écriture binaire 000111100100, c'est à dire au nombre 484.

Défi :

Et notre coffre dans tout ça ? À supposer que nous arrivions à trouver la stratégie optimale (qui comporte le moins de coups) pour allumer tous les interrupteurs, le code du coffre est la série des nombres correspondant à certains configurations d'interrupteurs obtenues lors de cette stratégie. L'entrée du défi donne le numéro de l'étape dans la stratégie, et le code à trouver représente la configuration des dinterrupteurs à cette étape.

Testez votre code:

Supposons que notre serrure ne comporte que 3 interrupteurs. La suite des configurations obtenue pour passer des interrupteurs éteints aux interrupteurs allumés est :
  • position 0 :
  • position 1 :
  • position 2 :
  • position 3 :
  • position 4 :
  • position 5 :

Si les nombres donnés en entrée était 1,2,4, il faudrait donc répondre 4, 6, 3 (valeur décimales des positions 1, 2 et 4).

Ce problème est tiré de c0d1ng UP 2014

Type de retour

Une séquence de 5 entiers

Entrée du problème

(2335, 882, 2060, 2099, 631)

Formulaire de réponse

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

Tags : cup14 algo récursivité cryptographie