Question

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

1. Строится двоичная запись числа $N$.
2. Эта запись обрабатывается по правилу:
   - если $N$ кратно 3, в конец дописываются три младших разряда полученной двоичной записи;
   - если $N$ не кратно 3, в конец дописывается двоичная запись числа $3 \cdot (N \bmod 3)$.

Полученная запись является двоичной записью числа $R$.

**Примеры:**
- $N = 5_{10} = 101_2$ → $R = 101110_2 = 46_{10}$
- $N = 9_{10} = 1001_2$ → $R = 1001001_2 = 73_{10}$

Найдите наибольшее число $N$, после обработки которого получается число $R < 100$.

Accepted Answer

22

Answer

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

**Программный подход:**

```python
for i in range(100, 0, -1):
    s = bin(i)[2:]  # двоичная запись N
    if i % 3 == 0:
        s += s[-3:]  # дописываем три младших разряда
    else:
        s += bin(3 * (i % 3))[2:]  # дописываем двоичную запись 3*(N mod 3)
    r = int(s, 2)  # переводим результат в десятичную
    if r < 100:
        print(i)
        break
```

**Аналитическое решение:**

Рассмотрим два случая в зависимости от остатка $N$ при делении на 3.

**Случай 1: $N \equiv 0 \pmod{3}$**

При дописывании трёх разрядов число увеличивается в 8 раз плюс значение трёх младших разрядов (от 0 до 7). Формула: $R = 8N + k$, где $0 \le k \le 7$.

Для $R < 100$: $8N < 100$, откуда $N < 12{,}5$. Проверим $N = 12$:
- $12_{10} = 1100_2$
- Дописываем три младших разряда: $100_2$
- Получаем $1100100_2 = 100_{10}$ — не подходит (не меньше 100).

Проверим $N = 9$:
- $9_{10} = 1001_2$
- Дописываем: $001_2$
- Получаем $1001001_2 = 73_{10}$ — подходит.

**Случай 2: $N \equiv 1 \pmod{3}$**

Дописываем $3 \cdot 1 = 3_{10} = 11_2$ (два разряда). Формула: $R = 4N + 3$.

Для $R < 100$: $4N + 3 < 100$, откуда $N < 24{,}25$. Проверим $N = 25$:
- $25 \cdot 4 + 3 = 103$ — не подходит.

Проверим $N = 22$:
- $22_{10} = 10110_2$
- Дописываем: $11_2$
- Получаем $1011011_2 = 91_{10}$ — подходит.

**Случай 3: $N \equiv 2 \pmod{3}$**

Дописываем $3 \cdot 2 = 6_{10} = 110_2$ (три разряда). Формула: $R = 8N + 6$.

Для $R < 100$: $8N + 6 < 100$, откуда $N < 11{,}75$. Проверим $N = 11$:
- $11_{10} = 1011_2$
- Дописываем: $110_2$
- Получаем $1011110_2 = 94_{10}$ — подходит.

Сравнивая все случаи: $\max(9, 22, 11) = 22$.

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