Question

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

1. Строится двоичная запись числа $N$.
2. К этой записи дописываются справа ещё два разряда по правилу:
   - складываются все цифры двоичной записи;
   - если сумма нечётная, дописывается `11`;
   - если сумма чётная, дописывается `00`.

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

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

Accepted Answer

115

Answer

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

Переведём 114 в двоичную систему: $114_{10} = 1110010_2$. Это число имеет 7 разрядов, значит оно не могло быть результатом алгоритма (результат всегда имеет чётное число разрядов, так как добавляются ровно 2 разряда к исходному числу).

Проверим числа, начиная с 1:

Для $N = 1$: двоичная запись `1`, количество единиц = 1 (нечётно), добавляем `11` → `111` = $7_{10}$.

Для $N = 2$: двоичная запись `10`, количество единиц = 1 (нечётно), добавляем `11` → `1011` = $11_{10}$.

Для $N = 3$: двоичная запись `11`, количество единиц = 2 (чётно), добавляем `00` → `1100` = $12_{10}$.

Продолжим перебор до получения числа, превышающего 114.

Для $N = 28$: двоичная запись `11100`, количество единиц = 3 (нечётно), добавляем `11` → `1110011` = $115_{10}$.

Число 115 превышает 114 и является результатом алгоритма.

Проверим на Python:

```python
for n in range(1, 1000):
    binary = bin(n)[2:]
    if binary.count('1') % 2 == 1:
        binary += '11'
    else:
        binary += '00'
    r = int(binary, 2)
    if r > 114:
        print(r)
        break
```

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