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 Championship 2004 Round 2

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Extra Spaces

Time limit: 0.5 second
Memory limit: 64 MB
A programmer Petrov took part in a programming contest outside his home university for the first time. There he suddenly understood that using an alien computer was not so nice. The computer he was working on even didn't have his favorite text editor. And, unfortunately, the program committee had given a text formatted by a nasty DOS text editor in such a way that all right ends of lines were at the same level. Of course, it had been performed by inserting extra spaces in many places. To read such a text was a torture for Petrov. It was his luck he found the FAR Manager, which could help to delete all these disgusting spaces replacing a combination of two spaces by one space. However, there were too many spaces, so such operation had to be performed several times, because after a replacement FAR did not search for the specified combination in the processed text. For example, if there are six successive spaces, then after one round of replacement the first two spaces are replaced by one space, the middle two spaces are replaced by one space, and the last two spaces are replaced by one space. As a result, we have three successive spaces. The second round of replacement deletes the first two of the three spaces and puts one space instead of them. So we need one more round of replacement, which replaces the remaining two spaces by one space. On the whole, three rounds of replacement are needed.
Petrov had already pressed Ctrl+F7, but than had a sudden thought: what if he first replaced each three spaces by one, and then each two spaces by one? So six successive spaces would be processed by two operations only! But which sequence of operations would be optimal if a text contained rows of spaces of a length not exceeding N?
Your task is to determine the minimal number of replacement rounds (each of which replaces rows of spaces of a certain length by one space) necessary for processing a text containing sequences of spaces of any length from 1 to L. You should also offer a scheme of the replacements. If there are many such schemes, then you should choose an optimal scheme among them, i.e., a scheme that also reduces any sequence of up to K spaces (KL) for a maximal possible K. If there are several optimal schemes, you may give any one of them.


The input contains an integer L, L < 2000000, which is the maximal length of a row of spaces in the text.


The first line of the output should contain an integer R, which is the minimal number of replacement rounds. The next R lines should describe an optimal scheme of replacements. Each of these lines must contain the length of row which are replaced by one space during the correspondent round.


Problem Author: Idea: Stanislav Vasilyev, prepared by Stanislav Vasilyev, Igor Goldberg
Problem Source: VIII Collegiate Students Urals Programming Contest. Yekaterinburg, March 11-16, 2004
To submit the solution for this problem go to the Problem set: 1324. Extra Spaces