Question

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

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

Например:
- для $N = 12 = 1100_2$: остаток 0, дописываем последние три цифры $100$, получаем $1100100_2 = 100_{10}$;
- для $N = 4 = 100_2$: остаток 1, $1 \cdot 3 = 3 = 11_2$, дописываем $11$, получаем $10011_2 = 19_{10}$.

Найти максимальное число $R$, не превышающее 137, которое может быть получено с помощью этого алгоритма.

Accepted Answer

127

Answer

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

Для каждого числа $N$:
1. Переводим $N$ в двоичную запись.
2. Вычисляем остаток $N \bmod 3$.
3. Если остаток равен 0, дописываем три последние двоичные цифры $N$.
4. Если остаток не равен 0, вычисляем $(	ext{остаток}) \cdot 3$, переводим в двоичную запись и дописываем.
5. Переводим полученную двоичную строку в десятичное число.
6. Проверяем, не превышает ли оно 137.

```python
for n in range(1000, 0, -1):
    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 <= 137:
        print(r)
        break
```

Программа перебирает числа от 1000 вниз до 1, применяет преобразование и выводит первое полученное значение $R$, которое не превышает 137.

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