ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Regional School Programming Contest 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Searching for the Dodecahedron

Time limit: 1.0 second
Memory limit: 64 MB
The Great Dodecahedron is an ancient powerful artifact. It is kept at the Temple of Five Polyhedra together with other magical artifacts. Many magicians tried to get it but to no avail, because a protection spell is put on the Dodecahedron.
There is a row of n pedestals in the fourth hall of the Temple. The pedestals are numbered from left to right starting from 1. The Great Dodecahedron is mounted on one of the pedestals, and the other pedestals support its exact copies, which have no magical power.
If a magician touches the real Dodecahedron, all the copies will disappear at once. If a magician touches a copy, nothing will happen, but, as soon as he removes the hand, the Dodecahedron will shift to a neighboring left or right pedestal and a copy will appear in its place.
Of course, the spell stops any unfair attempts to get the Dodecahedron, because any magician will die immediately if he touches several dodecahedra simultaneously.
Theoretical magicians from all over the world have been trying to invent an algorithm for finding the Great Dodecahedron for many centuries, but they have not succeeded yet. Can you help them?


The only input line contains the number n of pedestals in the fourth hall of the Temple of Five Polyhedra (2 ≤ n ≤ 100).


In the first line output the number m (m ≤ 1000) of touches necessary to find the Dodecahedron. In the second line output m integers separated with a space; these should be the numbers of pedestals in the order in which the dodecahedra mounted on them should be touched.
The algorithm must achieve the goal for any initial position of the artifact and for any of its admissible transitions. It is guaranteed that there exists at least one such algorithm in which at most one thousand touches are made.


2 2
Problem Author: Mikhail Rubinchik
Problem Source: Ural Regional School Programming Contest 2010
To submit the solution for this problem go to the Problem set: 1789. Searching for the Dodecahedron