Baguenaudier

Vous avez découvert un nouveau jeu très amusant. Celui-ci se joue sur un plateau de N cases alignées numérotées de 1 à N sur lesquelles on peut poser des jetons.

  • À tout moment, chaque case contient au plus un jeton.
  • Une case contenant un jeton est dite remplie, une case n'en contenant aucun est dite vide.
  • Au début de la partie, toutes les cases sont remplies.

Les règles du jeu sont les suivantes :

  • À tout moment on peut vider ou remplir la case 1.
  • Si la case 1 est remplie, alors on peut remplir ou vider la case 2. (Règle valable pour N >= 2)
  • Pour tout 3 <= K <= N, on peut remplir ou vider la case K lorsque les K - 2 premières cases sont vides et que la case K - 1 est remplie. (Règle valable pour N >= 3)

Le but du jeu est de vider toutes les cases. Vous avez décidé d'écrire un programme permettant de résoudre le jeu en un minimum de coups.

Limites de temps et de mémoire (Python)

  • Temps : 1,5 s sur une machine à 1 GHz.
  • Mémoire : 4 000 ko.

Contraintes

  • 1 <= N <= 18, où N est le nombre de cases du plateau.

Entrée

L'entrée est composée d'un unique entier : N, le nombre de cases du plateau.

Sortie

Votre programme doit afficher P lignes, avec P le nombre minimal de coups nécessaire pour finir le jeu.

Chacune des P lignes doit contenir un entier Pi compris entre 1 et N, décrivant le ie coup de votre séquence, par l'indice de la case remplie ou vidée à ce coup.

Exemple

entrée : 

4

sortie : 

2
1
4
1
2
1
3
1
2
1

Commentaires

Il s'agit ici de résoudre le jeu pour N = 4. Il faut au minimum 10 coups pour résoudre le jeu.

Voici une représentation correspondant à la séquence décrite par l'exemple de sortie :

Source : https://www.france-ioi.org/