Histoire

Le premier travail qu'Eurysthée demanda à Hercule fut de lui ramener la peau du lion de Némée. Le terrible animal vivait dans la forêt d'Argolide et terrorisait les habitants de la région.

L'antre du lion était une grotte possédant deux ouvertures vers l'extérieur. Pour s'attaquer à l'animal, Hercule devait boucher une des sorties, et acculer le lion dans son antre.

Une des sorties, construite par Minos et Dédale (un expert en labyrinthes), pouvait effectivement être fermée en actionnant un système de leviers assez complexe. Plusieurs leviers devaient être activés simultanément, en posant dessus des sortes de poids. Voici un schéma simplifié du système de verrouillage, ne contenant ici que 8 leviers :

Outre les leviers, Hercule avait à disposition des poids de plusieurs longueurs. En voici par exemple 4 :

Pour provoquer la fermeture de la porte, il fallait déposer les poids sur les leviers, de manière que sur chaque levier repose très exactement l'extrémité d'un seul poids, comme indiqué sur la figure suivante :

Pour le grand malheur d'Hercule, le vrai système n'était pas aussi simple, et il comportait un plus grand nombre de leviers et de poids. L'entrée du problème est constituée par la liste des longueurs des 20 poids, qu'il faut disposer sur les 40 leviers. Pour aider Hercule et résoudre le problème, il faut lui fournir l'ordre dans lequel disposer les poids, en donnant, pour chaque levier, la longueur du poids dont l'extrémité repose dessus.

Testez votre code

Dans l'exemple illustré ci-dessus, la liste des longueurs des poids est : 2, 2, 3, 5. Pour résoudre le problème, il suffit de décrire une configuration solution, comme par exemple 3, 5, 2, 3, 2, 2, 5,2