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

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

Пусть k — длина исходной двоичной записи, s — количество единиц, p — остаток s при делении на 2. Сначала дописываем p справа, и только затем заменяем два левых разряда на 10 при p = 0 или на 11 при p = 1.
При k ≥ 2 обозначим через t значение исходной записи без двух первых цифр: t = N mod 2ᵏ⁻². Тогда общая формула R = (2 + p) · 2ᵏ⁻¹ + 2t + p. Здесь mod означает остаток от деления. Для N = 1 отдельно получаем 1 → 11 → 11, то есть R = 3.
Новая запись имеет k + 1 разрядов и начинается с единицы, поэтому R ≥ 2ᵏ, а N меньше 2ᵏ. Следовательно, R ≥ N. Чётность N здесь не заменяет чётность количества единиц.

Обоснование конечного перебора.
Достаточно проверить 1 ≤ N ≤ 19. При N ≥ 20 нижняя оценка даёт R ≥ 1 · 20 = 20, что больше 19.
Такие N нарушают верхнюю границу из условия.

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход N, затем результат R:
N = 1, R = 3; N = 2, R = 7; N = 3, R = 4; N = 4, R = 13.
N = 5, R = 10; N = 6, R = 8; N = 7, R = 15; N = 8, R = 25.
N = 9, R = 18; N = 10, R = 20; N = 11, R = 31; N = 12, R = 16.
N = 13, R = 27; N = 14, R = 29; N = 15, R = 22; N = 16, R = 49.
N = 17, R = 34; N = 18, R = 36; N = 19, R = 55.

Наибольший допустимый вход: N = 12, R = 16. Его результат не больше 19; все большие входы в таблице нарушают условие, а входы за таблицей исключены оценкой.

Проверка выбранного входа: N = 12 = 1100₂.
Количество единиц равно 2; после добавления бита получаем 11000, после замены первых двух цифр — 10000.
Преобразованная запись: 10000₂.
R = 16 = 16.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем N.

Ответ: 12.