Двоичный автомат 8

Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:

1. Строится двоичная запись числа N.
2. Если сумма цифр десятичной записи заданного числа нечётна, то в конец двоичной записи дописывается 1, если чётна – 0.
3. Предыдущий пункт повторяется дважды для вновь полученных чисел.
4. Результатом работы алгоритма становится десятичная запись полученного числа R.

Например, для числа N = 17 алгоритм работает следующим образом:

1. Стоим двоичную запись: 17₁₀ = 10001₂.
2. Сумма цифр числа 17 – чётная, дописываем к двоичной записи 0, получаем 100010₂ = 34₁₀.
3. Сумма цифр числа 34 – нечётная, дописываем к двоичной записи 1, получаем 1000101₂ = 69₁₀.
4. Сумма цифр числа 69 – нечётная, дописываем к двоичной записи 1, получаем 10001011₂ = 139₁₀.
5. Результат работы алгоритма: R = 139.

Укажите минимальное число R, большее заданного целого числа M, которое может являться результатом работы этого алгоритма. В ответе запишите это число в десятичной системе счисления.

Входные данные

Входной файл INPUT.TXT содержит целое число M (1 ≤ M ≤ 10⁵).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]