Question

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

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

Например, для исходного числа $11 = 102_3$ результатом является число $22102_3 = 227$, а для исходного числа $12 = 110_3$ результатом является число $111002_3 = 353$.

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

Accepted Answer

6

Answer

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

Для каждого числа $N$:
1. Переводим $N$ в троичную систему.
2. Применяем правило преобразования в зависимости от остатка $N$ при делении на 3.
3. Переводим полученную троичную запись обратно в десятичную.
4. Проверяем, превышает ли результат 135.

```python
def to_base3(x):
    s = ''
    while x > 0:
        s += str(x % 3)
        x //= 3
    return s[::-1]

for N in range(100):
    s = to_base3(N)
    if N % 3 == 0:
        s = '1' + s + '02'
    else:
        s = to_base3((N % 3) * 4) + s
    R = int(s, 3)
    if R > 135:
        print(N)
        break
```

Проверим вычисления для малых значений:
- $N = 1$: $1_3 = 1$, остаток 1, $1 \cdot 4 = 4 = 11_3$, результат $11 \cdot 1_3 = 121_3 = 16_{10}$.
- $N = 2$: $2_3 = 2$, остаток 2, $2 \cdot 4 = 8 = 22_3$, результат $22 \cdot 2_3 = 222_3 = 26_{10}$.
- $N = 3$: $3_3 = 10$, делится на 3, результат $1 \cdot 10 \cdot 02_3 = 11002_3 = 99_{10}$.
- $N = 4$: $4_3 = 11$, остаток 1, $1 \cdot 4 = 4 = 11_3$, результат $11 \cdot 11_3 = 11011_3 = 109_{10}$.
- $N = 5$: $5_3 = 12$, остаток 2, $2 \cdot 4 = 8 = 22_3$, результат $22 \cdot 12_3 = 22012_3 = 227_{10}$.
- $N = 6$: $6_3 = 20$, делится на 3, результат $1 \cdot 20 \cdot 02_3 = 12002_3 = 135_{10}$.

Для $N = 6$ получаем $R = 135$, что не превышает 135. Продолжаем:
- $N = 7$: $7_3 = 21$, остаток 1, $1 \cdot 4 = 4 = 11_3$, результат $11 \cdot 21_3 = 11021_3 = 136_{10}$.

Число 136 больше 135, поэтому минимальное $N$ равно 7.

Однако проверим ещё раз вычисление для $N = 6$:
$6 = 20_3$, делится на 3, получаем $1 \cdot 20 \cdot 02_3 = 12002_3$.
$12002_3 = 1 \cdot 81 + 2 \cdot 27 + 0 \cdot 9 + 0 \cdot 3 + 2 = 81 + 54 + 2 = 137_{10}$.

Число 137 больше 135, поэтому минимальное $N$ равно 6.

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