На вход алгоритма подаётся натуральное число N N. Алгоритм строит по нему новое число R R следующим образом. Строится двоичная запись числа N N. Далее эта запись обрабатывается по…
На вход алгоритма подаётся натуральное число N N. Алгоритм строит по нему новое число R R следующим образом. Строится двоичная запись числа N N. Далее эта запись обрабатывается по следующему правилу: а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 00, а затем два левых разряда заменяются на 11 б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 01, а затем два левых разряда заменяются на 10 Полученная таким образом запись является двоичной записью искомого числа R R. Например, для исходного числа 6 10 = 110 2 6 10 =110 2 результатом является число 11000 2 = 24 10 11000 2 =24 10 , а для исходного числа 4 10 = 100 2 4 10 =100 2 результатом является число 10001 2 = 17 10 10001 2 =17 10 . Укажите минимальное число N N, после обработки которого с помощью этого алгоритма получается число R R, большее 96. В ответе запишите это число в десятичной системе счисления.
Ответ: 17
Пояснение пошагово
Обозначим длину двоичной записи N как k (N в диапазоне [2^{k-1}, 2^{k}-1]), и запишем N в виде s = b1 b2 ... bk, где b1 = 1. Пусть m = b3 b4 ... bk, и его числовое значение обозначим как V_m (V_m ∈ [0, 2^{k-2}-1], если k ≥ 2).
Правило преобразования даёт:
- если сумма цифр в двоичной записи (то есть количество единиц) парна, то R_bits = 11 · m · 00, то есть R = 3·2^k + 4·V_m;
- если сумма цифр нечётна, то R_bits = 10 · m · 01, то есть R = 2^{k+1} + 4·V_m + 1.
Примечание: это верно для k ≥ 2. Для k = 1 отдельно, N = 1 даёт R = 5.
- Проверим возможные k на предмет возможности превысить 96:
- k = 1: максимум R = 5.
- k = 2: R ∈ {9, 12}.
- k = 3: максимум R = 28.
- k = 4: максимум R = 60.
Вообще для k ≤ 4 R ≤ 60 < 96. Значит минимальный N с R > 96 имеет k ≥ 5.
- Рассмотрим k = 5. Тогда R = 96 + 4·V_m (для чётной суммы единиц) или R = 65 + 4·V_m (для нечётной), с V_m ∈ [0, 7].
Чтобы получить R > 96, необходима чётная сумма единиц и V_m ≥ 1. Тогда минимальное R = 96 + 4·1 = 100.
- Теперь найдём минимальное N при k = 5, чётной сумме единиц и V_m = 1. Значение V_m = 1 означает, что m = b3 b4 b5 = 001. Чтобы N был минимальным, выбираем b2 = 0. Получаем двоичное N = b1 b2 b3 b4 b5 = 1 0 0 0 1 = 10001_2.
Проверка:
- N = 17, двоичное представление 10001, сумма единиц = 2 (чётная).
- Применение алгоритма даёт R_bits = 11 001 00 = 1100100_2 = 100_10, т. е. R = 100 > 96.
- Никакое N с меньшим k не даст R > 96, а при k = 5 минимальный подходящий кандидат — N = 17, который действительно даёт R > 96.
Ответ: 17
