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

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

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

Обоснование конечного перебора.
Достаточно проверить 1 ≤ N ≤ 25. При N ≥ 26 нижняя оценка даёт R ≥ 4 · 26 = 104, что больше 102.
В таблице уже есть допустимый результат R = 102; все пропущенные большие 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.
N = 17, R = 68; N = 18, R = 72; N = 19, R = 78; N = 20, R = 80.
N = 21, R = 86; N = 22, R = 90; N = 23, R = 92; N = 24, R = 96.
N = 25, R = 102.

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

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

Ответ: 102.