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.

TIME AND MEMORY LIMITS (Python)

  • Time: 1.5s on a 1GHz machine.
  • Memory: 4,000 KB.

CONSTRAINTS

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

INPUT

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

OUTPUT

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.

EXAMPLE

input: 

4

output: 

2
1
4
1
2
1
3
1
2
1

COMMENTS

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.