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

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

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

Обоснование конечного перебора.
Достаточно проверить 1 ≤ N ≤ 16. При N ≥ 17 нижняя оценка даёт R ≥ 4 · 17 = 68, что больше 66.
В таблице уже есть допустимый результат R = 66; все пропущенные большие N дают ещё больший R и улучшить минимум не могут.

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход 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.

Среди результатов, которые больше 63, наименьший равен 66. Он достигается при N = 16.

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

Ответ: 66.