Question

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

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

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

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

Accepted Answer

21

Answer

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

Алгоритм работает так:
1. Переводим число $N$ в двоичную систему.
2. Подсчитываем количество единиц в текущей записи, добавляем остаток от деления на 2 в конец.
3. Повторяем процесс ещё раз для получения второго дополнительного разряда.
4. Переводим полученную двоичную запись обратно в десятичную систему.
5. Проверяем, превышает ли результат 85.

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

Проверим на примере $N = 21$:
- Двоичная запись: $10101_2$
- Количество единиц: 3, остаток от деления на 2: 1. Получаем $101011_2$
- Количество единиц: 4, остаток от деления на 2: 0. Получаем $1010110_2$
- Переводим в десятичную: $1010110_2 = 86_{10}$

Число 86 больше 85, и это первое такое число, полученное из минимального входного значения.

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