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

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

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

Обоснование конечного перебора.
Ниже проверяются все натуральные N от 1 до 112 включительно. Для минимального N достаточно найти первый подходящий вход: ни одно большее N уже не может улучшить ответ.

Полный расчёт на выбранном отрезке по приведённым формулам. В каждой паре сначала указан вход 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.
N = 101, R = 404; N = 102, R = 408; N = 103, R = 414; N = 104, R = 418.
N = 105, R = 420; N = 106, R = 424; N = 107, R = 430; N = 108, R = 432.
N = 109, R = 438; N = 110, R = 442; N = 111, R = 444; N = 112, R = 450.

Первый вход, для которого R больше 445: N = 112, R = 450. Все меньшие N есть в таблице и не удовлетворяют требованию.

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

Ответ: 112.