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

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

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

Обоснование конечного перебора.
Достаточно проверить 1 ≤ N ≤ 100. При N ≥ 101 нижняя оценка даёт R ≥ 4 · 101 = 404, что больше 402.
В таблице уже есть допустимый результат R = 402; все пропущенные большие 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; N = 26, R = 106; N = 27, R = 108; N = 28, R = 114.
N = 29, R = 116; N = 30, R = 120; N = 31, R = 126; N = 32, R = 130.
N = 33, R = 132; N = 34, R = 136; N = 35, R = 142; N = 36, R = 144.
N = 37, R = 150; N = 38, R = 154; N = 39, R = 156; N = 40, R = 160.
N = 41, R = 166; N = 42, R = 170; N = 43, R = 172; N = 44, R = 178.
N = 45, R = 180; N = 46, R = 184; N = 47, R = 190; N = 48, R = 192.
N = 49, R = 198; N = 50, R = 202; N = 51, R = 204; N = 52, R = 210.
N = 53, R = 212; N = 54, R = 216; N = 55, R = 222; N = 56, R = 226.
N = 57, R = 228; N = 58, R = 232; N = 59, R = 238; N = 60, R = 240.
N = 61, R = 246; N = 62, R = 250; N = 63, R = 252; N = 64, R = 258.
N = 65, R = 260; N = 66, R = 264; N = 67, R = 270; N = 68, R = 272.
N = 69, R = 278; N = 70, R = 282; N = 71, R = 284; N = 72, R = 288.
N = 73, R = 294; N = 74, R = 298; N = 75, R = 300; N = 76, R = 306.
N = 77, R = 308; N = 78, R = 312; N = 79, R = 318; N = 80, R = 320.
N = 81, R = 326; N = 82, R = 330; N = 83, R = 332; N = 84, R = 338.
N = 85, R = 340; N = 86, R = 344; N = 87, R = 350; N = 88, R = 354.
N = 89, R = 356; N = 90, R = 360; N = 91, R = 366; N = 92, R = 368.
N = 93, R = 374; N = 94, R = 378; N = 95, R = 380; N = 96, R = 384.
N = 97, R = 390; N = 98, R = 394; N = 99, R = 396; N = 100, R = 402.

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

Проверка выбранного входа: N = 100 = 1100100₂.
Количество единиц равно 3; первый добавляемый бит 1, второй 0.
Преобразованная запись: 110010010₂.
R = 256 + 128 + 16 + 2 = 402.
Полученное значение удовлетворяет условию. Полный перебор с доказанной границей подтверждает требуемый экстремум. В ответ записываем R.

Ответ: 402.