Question

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

1. Строится двоичная запись числа $N$.
2. Далее эта запись обрабатывается по следующему правилу:
   - если число $N$ делится на 3, то в этой записи дописываются справа три последние двоичные цифры;
   - если число $N$ на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
3. Полученная таким образом запись является двоичной записью искомого числа $R$.
4. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа $12 = 1100_2$ результатом является число $11001100_2 = 204$, а для исходного числа $4 = 100_2$ результатом является число $10011_2 = 19$.

Укажите минимальное число $N$, после обработки которого с помощью этого алгоритма получается число $R$, не меньшее чем 76.

Accepted Answer

11

Answer

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

Для каждого числа $N$:
1. Переводим $N$ в двоичную запись.
2. Проверяем делимость $N$ на 3:
   - если делится, дописываем три последние двоичные цифры;
   - если не делится, вычисляем остаток $r = N \bmod 3$, умножаем на 3, переводим в двоичную и дописываем.
3. Полученную двоичную строку переводим в десятичное число.
4. Если результат $\geq 76$, выводим $N$ и завершаем поиск.

```python
for n in range(1, 1000):
    s = bin(n)[2:]
    if n % 3 == 0:
        s += bin(n)[-3:]
    else:
        s += bin((n % 3) * 3)[2:]
    r = int(s, 2)
    if r >= 76:
        print(n)
        break
```

Проверим вручную для $N = 11$:
- $11 = 1011_2$
- $11 \bmod 3 = 2$, остаток $2 	imes 3 = 6 = 110_2$
- Новая запись: $1011110_2 = 64 + 16 + 8 + 4 + 2 = 94$
- $94 \geq 76$ ✓

Для $N = 10$:
- $10 = 1010_2$
- $10 \bmod 3 = 1$, остаток $1 	imes 3 = 3 = 11_2$
- Новая запись: $101011_2 = 32 + 8 + 2 + 1 = 43$
- $43 < 76$ ✗

Таким образом, минимальное число — 11.

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