Question

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

1. Строится двоичная запись числа $N$.
2. Если $N$ чётное, то в конец записи (справа) дописывается 0, в начало — 1; если $N$ нечётное, в конец и начало дописывается по две единицы.
3. Результат переводится в десятичную систему и выводится на экран.

**Пример.** Дано число $N = 13$. Алгоритм работает следующим образом:
1. Двоичная запись числа $N$: $1101_2$.
2. Число нечётное, следовательно, по две единицы по краям — $11110111_2$.
3. На экран выводится число 247.

Укажите наименьшее число, большее 52, которое может являться результатом работы автомата.

Accepted Answer

56

Answer

Идея решения: результат автомата всегда оканчивается либо на `00` (для чётного исходного числа), либо на `11` (для нечётного), поэтому достаточно проверить последовательно числа, начиная с 53, и найти первое, удовлетворяющее этому условию и имеющее корректную структуру.

**Анализ структуры результата:**

Число, полученное на выходе автомата, должно оканчиваться либо на $00_2$ (дописано к чётному числу), либо на $11_2$ (дописано к нечётному числу). Кроме того, оно должно начинаться с 1 (для чётного) или с 11 (для нечётного).

- $53_{10} = 110101_2$ — оканчивается на 01, не подходит.
- $54_{10} = 110110_2$ — оканчивается на 10, не подходит.
- $55_{10} = 110111_2$ — оканчивается на 11, но если это результат из нечётного числа, то исходное число — $0111_2$, что начинается с 0 (невозможно).
- $56_{10} = 111000_2$ — оканчивается на 00, начинается с 1. Исходное число: $1100_2 = 12_{10}$ (чётное). Проверка: $1100_2$ → добавляем 1 слева и 0 справа → $111000_2 = 56_{10}$. ✓

**Альтернативное решение на Python:**

```python
a = []
for n in range(1, 100):
    s = bin(n)[2:]
    if n % 2 == 0:
        s = "1" + s + "0"
    else:
        s = "11" + s + "11"
    r = int(s, 2)
    if r > 52:
        a.append(r)
print(min(a))
```

Программа перебирает натуральные числа от 1 до 99, применяет к каждому алгоритм автомата, собирает результаты, большие 52, и выводит минимальный из них.

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