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

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

Пусть 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 ≤ 57. При N ≥ 58 нижняя оценка даёт R ≥ 4 · 58 = 232, что больше 228.
В таблице уже есть допустимый результат R = 228; все пропущенные большие 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; N = 16, R = 96.
N = 17, R = 455; N = 18, R = 100; N = 19, R = 463; N = 20, R = 104.
N = 21, R = 471; N = 22, R = 108; N = 23, R = 479; N = 24, R = 112.
N = 25, R = 487; N = 26, R = 116; N = 27, R = 495; N = 28, R = 120.
N = 29, R = 503; N = 30, R = 124; N = 31, R = 511; N = 32, R = 192.
N = 33, R = 903; N = 34, R = 196; N = 35, R = 911; N = 36, R = 200.
N = 37, R = 919; N = 38, R = 204; N = 39, R = 927; N = 40, R = 208.
N = 41, R = 935; N = 42, R = 212; N = 43, R = 943; N = 44, R = 216.
N = 45, R = 951; N = 46, R = 220; N = 47, R = 959; N = 48, R = 224.
N = 49, R = 967; N = 50, R = 228; N = 51, R = 975; N = 52, R = 232.
N = 53, R = 983; N = 54, R = 236; N = 55, R = 991; N = 56, R = 240.
N = 57, R = 999.

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

Проверка выбранного входа: N = 50 = 110010₂.
Преобразованная запись: 11100100₂.
R = 128 + 64 + 32 + 4 = 228.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем R.

Ответ: 228.