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.

LAIKO IR ATMINTIES RIBOJIMAI (Python)

  • Laiko ribojimas: 1.5 sek., procesorius: 1GHz.
  • Atmintis: 4,000 KB.

RIBOJIMAI

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

PRADINIAI DUOMENYS

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

REZULTATAI

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.

PAVYZDYS

pradiniai duomenys: 

4

rezultatai: 

2
1
4
1
2
1
3
1
2
1

KOMENTARAI

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 :

Autorystė priklauso šios svetainės kūrėjams.