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

Open Ural FU Personal Contest 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Programmer Casino

Time limit: 1.0 second
Memory limit: 64 MB
The Macau city is referred to as the “Oriental Monte Carlo”. There are more than thirty casinos in Macau. Every year they lure millions of gamblers from China and from other countries. The gambling industry makes up for about 40% of the city's GDP.
Vova learned from his friends in Guangzhou that Macau has special casinos for programmers only. Vova found that quite interesting and he immediately decided to visit a programmer casino. One such casino was located by Vova's hotel, so in the evening he took some cash and went there.
Indeed, there must have been programmers sitting at the casino tables, because the tables had no cards or pieces. Instead, each player had a notepad lying in front of him. A player wrote some numbers in his notepad. Vova was explained that the game goes like this. First each player writes a number one on a clear notepad page. Then the croupier starts reading out a sequence of zeroes and ones, one digit at a time. If the croupier reads out a number zero, all players add a zero to the end of the last number in their pages. And if the croupier reads out a number one, then the player can either add this number one to the end of the last number or write it on a new line, thus starting a new number. After the croupier stops reading out the digits, each player converts all his binary numbers into decimals, then glues them all into a single decimal number in the order, in which they were recorded. The player with the minimum resulting number wins.
For example, if the croupier reads out the sequence of 1011100101, the first player writes binary letters 1, 1011 and 100101 decimals 1, 11 and 37), and the second player writes 110, 11100 and 101 (decimal 6, 28 and 5), then the winner is the second player as 6285 is less than 11137.
Before joining in the game, Vova decided to learn to play optimally well for the simple case when the croupier's sequence is represented as a binary record of all integers one by one from 2 to n (in the above given example n was equal to five). But as Vova failed to quickly come up with the optimal strategy, he asked you to help him.


The single line contains an integer n (2 ≤ n ≤ 100 000).


In the first line print, how many numbers Vova should write down if he plays optimally well. In the second line print the numbers' lengths in bits in the order they are written. If there are multiple solutions that result in the minimum decimal number, print any of them.


1 10


In the sample you need to write down all the digits the croupier reads out into the second number. In this case after the numbers are converted to decimals and glued together, we get number 1741.
Problem Author: Ilya Zvigintsev
Problem Source: Open Ural FU Personal Contest 2013
To submit the solution for this problem go to the Problem set: 1967. Programmer Casino