ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1967. Казино для программистов

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Город Макао называют «Монте-Карло Востока». В Макао работают более тридцати казино, приманивающих ежегодно миллионы игроков как из Китая, так и из других стран. Индустрия азартных игр формирует около 40% ВВП города.
От своих друзей из Гуанчжоу Вова узнал, что в Макао есть специальные казино, в которых играют только программисты. Это показалось Вове очень интересным, и он решил непременно сходить в такое казино. Одно из подобных заведений было расположено неподалёку от отеля, где остановился Вова, поэтому вечером он, пополнив запас наличных денег, пошёл в казино.
За игровыми столами в казино, по-видимому, и вправду сидели программисты, потому что ни карт, ни фишек на столах не было, но перед каждым игроком лежал блокнот, в который тот записывал какие-то числа. Как пояснили Вове, смысл игры заключался в следующем. Сначала каждый игрок записывал на чистом листе блокнота одну единицу. После этого крупье начинал зачитывать последовательность из нулей и единиц, называя по одной цифре. Если крупье называл ноль, все игроки дописывали ноль в конец последнего числа, выписанного на их листе. Если же крупье называл единицу, то игрок мог либо дописать эту единицу в конец последнего числа, либо записать её в новой строке, начав тем самым с неё новое число. После того как крупье прекращал зачитывать цифры, каждый игрок переводил все записанные им двоичные числа в десятичный вид, затем склеивал их все в одно десятичное число в том порядке, в котором они были записаны. Выигрывал тот игрок, который получал в результате наименьшее число.
Например, если крупье зачитал последовательность 1011100101, первый игрок записал двоичные числа 1, 1011 и 100101 (десятичные 1, 11 и 37), а второй игрок записал 110, 11100 и 101 (десятичные 6, 28 и 5), то победу одержал второй игрок, поскольку 6285 меньше 11137.
Перед тем как сесть за игровой стол, Вова решил научиться оптимально играть для простого случая, когда последовательность крупье представляет собой запись в двоичном виде всех целых чисел подряд от 2 до n (в разобранном выше примере n равнялось пяти). Но быстро придумать оптимальную стратегию Вова не смог, поэтому он обратился за помощью к вам.

Исходные данные

В единственной строке записано целое число n (2 ≤ n ≤ 100 000).

Результат

В первой строке выведите количество чисел, которые должен записать Вова в случае его оптимальной игры. Во второй строке выведите длины этих чисел в битах в том порядке, в котором числа нужно записать. Если есть несколько решений, дающих в результате наименьшее десятичное число, выведите любое из них.

Пример

исходные данныерезультат
5
2
1 10

Замечания

В примере нужно записать все цифры, зачитанные крупье, во второе число. В этом случае после перевода чисел в десятичную систему и их склейки получится число 1741.
Автор задачи: Илья Звигинцев
Источник задачи: Открытое личное первенство УрФУ по программированию 2013