Question

Автомат обрабатывает натуральное число $N$ по следующему алгоритму:

1. Строится двоичная запись числа $N$.
2. К этой записи дописываются справа два разряда по правилу: если $N$ чётное, дописывается `10`, иначе дописывается `01`.

Например, двоичная запись $1001_2$ числа 9 преобразуется в $100101_2$.

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

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

Accepted Answer

101

Answer

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

Проверим числа, начиная с 102 и идя вниз:

$102_{10} = 1100110_2$ — это число имеет 7 разрядов. Если оно результат алгоритма, то исходное число имело 5 разрядов. Проверим: исходное число должно быть либо $11001_2 = 25_{10}$ (если чётное, добавляем `10`), либо $11001_2 = 25_{10}$ (если нечётное, добавляем `01`). Число 25 нечётное, поэтому добавляем `01`: $1100101_2 = 101_{10}$. Это не 102, значит 102 не результат.

$101_{10} = 1100101_2$ — это число имеет 7 разрядов. Исходное число: $11001_2 = 25_{10}$. Число 25 нечётное, добавляем `01`: $1100101_2 = 101_{10}$. Совпадает! Значит, 101 является результатом алгоритма.

Проверим программой:

```python
for n in range(100, 1, -1):
    s = bin(n)[2:]
    if n % 2 == 0:
        s += "10"
    else:
        s += "01"
    r = int(s, 2)
    if r <= 102:
        print(r)
        break
```

Программа перебирает числа от 100 вниз, применяет алгоритм и выводит первое число, результат которого не превышает 102.

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