Задание EGEINF193F62: Преобразование записи числа

Дано: N — натуральное число. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 89. В ответе это число запишите в десятичной системе счисления.

Пусть s — количество единиц в двоичной записи N, p — остаток s при делении на 2. Первый дописанный бит равен p. Сумма s + p всегда чётна, поэтому второй дописанный бит равен 0. Получаем окончание 00 при чётном s и 10 при нечётном s.
Общая формула: R = 4N + 2p.
Следовательно, R ≥ 4N. Проверяется чётность суммы цифр, а не самого N.

Обоснование конечного перебора.
Ниже проверяются все натуральные N от 1 до 22 включительно. Для минимального N достаточно найти первый подходящий вход: ни одно большее N уже не может улучшить ответ.

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход N, затем результат R:
N = 1, R = 6; N = 2, R = 10; N = 3, R = 12; N = 4, R = 18.
N = 5, R = 20; N = 6, R = 24; N = 7, R = 30; N = 8, R = 34.
N = 9, R = 36; N = 10, R = 40; N = 11, R = 46; N = 12, R = 48.
N = 13, R = 54; N = 14, R = 58; N = 15, R = 60; N = 16, R = 66.
N = 17, R = 68; N = 18, R = 72; N = 19, R = 78; N = 20, R = 80.
N = 21, R = 86; N = 22, R = 90.

Первый вход, для которого R больше 89: N = 22, R = 90. Все меньшие N есть в таблице и не удовлетворяют требованию.

Проверка выбранного входа: N = 22 = 10110₂.
Количество единиц равно 3; первый добавляемый бит 1, второй 0.
Преобразованная запись: 1011010₂.
R = 64 + 16 + 8 + 2 = 90.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем N.

Ответ: 22.