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

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

Рассматриваем остаток N при делении на 3. Если он равен 1, дописывается запись числа 3, то есть 11; если равен 2, дописывается запись числа 6, то есть 110. Для кратного 3 числа с хотя бы тремя двоичными цифрами значение последних трёх цифр равно остатку N при делении на 8.
Общие формулы: R = 4N + 3 при остатке 1; R = 8N + 6 при остатке 2; R = 8N + (N mod 8) при кратном 3 числе N ≥ 6. Здесь mod означает остаток от деления.
Во всех ветвях R ≥ 4N. Для малого N = 3 запись 11 содержит лишь две цифры: копирование имеющихся цифр даёт 1111₂ = 15, дополнение копии до 011 даёт 11011₂ = 27. Оба значения ниже рассматриваемой границы и не меняют искомый экстремум. В таблице для N = 3 указано 15; остальные строки не зависят от этой особенности формулировки.

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

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход N, затем результат R:
N = 1, R = 7; N = 2, R = 22; N = 3, R = 15; N = 4, R = 19.
N = 5, R = 46; N = 6, R = 54; N = 7, R = 31; N = 8, R = 70.
N = 9, R = 73; N = 10, R = 43; N = 11, R = 94; N = 12, R = 100.
N = 13, R = 55; N = 14, R = 118; N = 15, R = 127; N = 16, R = 67.
N = 17, R = 142; N = 18, R = 146; N = 19, R = 79; N = 20, R = 166.
N = 21, R = 173; N = 22, R = 91; N = 23, R = 190; N = 24, R = 192.
N = 25, R = 103; N = 26, R = 214; N = 27, R = 219; N = 28, R = 115.
N = 29, R = 238; N = 30, R = 246; N = 31, R = 127; N = 32, R = 262.
N = 33, R = 265; N = 34, R = 139; N = 35, R = 286; N = 36, R = 292.
N = 37, R = 151; N = 38, R = 310; N = 39, R = 319; N = 40, R = 163.
N = 41, R = 334; N = 42, R = 338; N = 43, R = 175; N = 44, R = 358.
N = 45, R = 365; N = 46, R = 187; N = 47, R = 382; N = 48, R = 384.
N = 49, R = 199; N = 50, R = 406; N = 51, R = 411; N = 52, R = 211.

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

Проверка выбранного входа: N = 49 = 110001₂.
Преобразованная запись: 11000111₂.
R = 128 + 64 + 4 + 2 + 1 = 199.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем R.

Ответ: 199.