Prologin
2024
Énoncé¶
Avec les informations tout juste récupérées, Valérian commence à se poser des questions sur l'encodage des nombres qu'Oscar lui indiquait, avant de se rendre compte qu'Oscar lisait le manuel d'instructions de sa machine à laver ! (qui bien sûr ne suit pas le même système d'encodage pour la température que notre machine pour l'année…) Personne ne se souvenant du système d'encodage exact, les jeunes vont désespérément tenter de retourner au présent pour récupérer le manuel d'instructions… Même sans connaître l'encodage, ils savent que grâce au mode relatif, ils ne peuvent qu'avancer dans le temps. Alors Valérian décide de faire une combinaison aléatoire pour voir où ça les mène.
Les jeunes sortent alors de leur machine à voyager dans le temps et tombent nez à nez avec ce qui semble être un mathématicien Perse des années 800. Amusé par l'étrange machine par laquelle nos aventuriers viennent de s'extirper, le mathématicien leur remet un coffre, fermé par plusieurs loquets, demandant en échange de pouvoir étudier un peu la machine. Le mathématicien semble affirmer que le contenu du coffre va les intéresser, alors nos amis se mettent au travail pour ouvrir le coffre et emporter son contenu.
Le coffre est maintenu fermé par $N$ loquets. Chaque loquet peut être "ouvert" ($1$) ou "fermé" ($0$). Initialement, les $N$ loquets sont fermés. Pour ouvrir le coffre, il faut réussir à avoir les $N$ loquets ouverts simultanément.
Le premier loquet, en position $1$, est modifiable à volonté, sans condition. Cependant, pour pouvoir modifier n'importe quel autre loquet en position $i$, il faut que :
- le loquet en position $i-1$ soit ouvert ($1$)
- tous les loquets entre les positions $1$ et $i-2$ (inclus) soient fermés ($0$)
Aidez nos amis en déterminant la plus petite suite de coup permettant d'ouvrir le coffre.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : N, le nombre de loquets.
Sortie¶
Afficher la suite de coup optimale pour ouvrir le coffre. Chaque coup doit être représenté sur une ligne par deux entiers séparés par un espace : le premier entier, compris entre $1$ et $N$, représente la position du loquet affecté. Le second entier vaut $0$ si ce loquet est refermé, ou $1$ si ce loquet est ouvert.
Contraintes¶
- $1 \le N \le 20$