Question

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом:

1. Строится двоичная запись числа $N$.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
   - а) складываются все цифры двоичной записи числа $N$, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись $11100_2$ преобразуется в запись $111001_2$;
   - б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы её цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа $N$) является двоичной записью искомого числа $R$.

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

Accepted Answer

102

Answer

Идея решения: перебрать все натуральные числа, применить к ним алгоритм преобразования и найти первое число, превышающее 97.

Заметим, что если число $N$ нечётное (в двоичной записи оканчивается на 1), то количество единиц нечётно, и первый добавляемый разряд — 1. Если число чётное, первый разряд — 0. Аналогично для второго разряда.

Переберём натуральные числа $N$ от 1 до 99, для каждого:
1. Переведём $N$ в двоичную систему.
2. Подсчитаем количество единиц в двоичной записи.
3. Добавим остаток от деления этого количества на 2.
4. Подсчитаем количество единиц в новой записи и добавим остаток от деления на 2.
5. Переведём полученную двоичную запись в десятичную систему.
6. Если результат превышает 97, выведем его и остановимся.

```python
for n in range(1, 100):
    b = bin(n)[2:]
    b = b + str(b.count('1') % 2)
    b = b + str(b.count('1') % 2)
    r = int(b, 2)
    if r > 97:
        print(r)
        break
```

Проверим вручную для нескольких значений:
- $N = 12$: $12_{10} = 1100_2$ (две единицы) → $11001_2$ (три единицы) → $110011_2 = 51_{10}$ (не подходит).
- $N = 25$: $25_{10} = 11001_2$ (три единицы) → $110011_2$ (четыре единицы) → $1100110_2 = 102_{10}$ (подходит, превышает 97).

Задание №5Системы счисления и арифметикаЕГЭ по информатике