Question

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

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

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

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

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

Accepted Answer

29

Answer

Идея решения: переведём 115 в двоичную систему, удалим два правых разряда, чтобы получить кандидата на исходное число, затем проверим, какое минимальное $N$ даёт результат больше 115.

Переведём 115 в двоичную систему: $115_{10} = 1110011_2$.

Если удалить два правых разряда из $1110011_2$, получим $11100_2 = 28_{10}$. Проверим: число 28 чётное, поэтому алгоритм добавит «00», получится $1110000_2 = 112_{10}$. Это не больше 115.

Попробуем $N = 29_{10} = 11101_2$. Число 29 нечётное, поэтому добавим «11»: $1110111_2 = 119_{10}$. Поскольку $119 > 115$, это подходит.

Проверим, что 29 — минимальное. Для $N = 28$ получаем 112 (не подходит). Для $N = 29$ получаем 119 (подходит).

Вот программа на Python для проверки:

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

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

![Рисунок](https://ege.sdamgia.ru/formula/svg/e5/e5214ea050b009f5967855758cfa1f60.svg)

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