Question

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

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

Например, двоичная запись $100_2$ числа 4 преобразуется в $10001_2$, а двоичная запись $111_2$ числа 7 преобразуется в $11110_2$.

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

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

Accepted Answer

105

Answer

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

Проверим несколько чисел вручную:

- $N = 26_{10} = 11010_2$ (чётное) → дописываем «01» → $1101001_2 = 105_{10}$
- $N = 25_{10} = 11001_2$ (нечётное) → дописываем «10» → $1100110_2 = 102_{10}$ (не подходит, равно 102)
- $N = 24_{10} = 11000_2$ (чётное) → дописываем «01» → $1100001_2 = 97_{10}$ (меньше 102)

Проверим числа, дающие результат больше 102:

- $103_{10} = 1100111_2$ — последние два разряда «11», что невозможно по правилам алгоритма.
- $104_{10} = 1101000_2$ — последние два разряда «00», что невозможно по правилам алгоритма.
- $105_{10} = 1101001_2$ — последние два разряда «01», что соответствует чётному исходному числу. Удаляя последние два разряда, получаем $11010_2 = 26_{10}$ (чётное) ✓

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

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

Программа выведет 105.

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