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

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

Пусть k — длина двоичной записи N; тогда 2ᵏ больше N. В чётной ветви префикс 1 занимает разряд k + 1, а нуль справа сдвигает N на один разряд. В нечётной ветви дописывается по две единицы с обеих сторон.
Общие формулы: R = 2ᵏ⁺¹ + 2N при чётном N; R = 3 · 2ᵏ⁺² + 4N + 3 при нечётном N.
В чётной ветви R больше 4N, в нечётной — больше 16N. Следовательно, R ≥ 4N.

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

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход N, затем результат R:
N = 1, R = 31; N = 2, R = 12; N = 3, R = 63; N = 4, R = 24.
N = 5, R = 119; N = 6, R = 28; N = 7, R = 127; N = 8, R = 48.
N = 9, R = 231; N = 10, R = 52; N = 11, R = 239; N = 12, R = 56.
N = 13, R = 247; N = 14, R = 60; N = 15, R = 255.

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

Проверка выбранного входа: N = 12 = 1100₂.
Преобразованная запись: 111000₂.
R = 32 + 16 + 8 = 56.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем R.

Ответ: 56.