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

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

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

Обоснование конечного перебора.
Достаточно проверить 1 ≤ N ≤ 14. При N ≥ 15 нижняя оценка даёт R ≥ 4 · 15 = 60, что больше 58.
В таблице уже есть допустимый результат R = 58; все пропущенные большие 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.

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

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

Ответ: 58.