Question

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

1. Строится троичная запись числа $N$.
2. Если $N$ кратно 3, то в конец записи дописываются три последние цифры этой записи.
3. Если $N$ не кратно 3, то остаток от деления $N$ на 3 умножается на 3, переводится в троичную систему и дописывается к числу.

Полученная таким образом запись является троичной записью числа $R$. Укажите минимальное число $N$, после обработки которого алгоритм получает число, большее 150.

Accepted Answer

9

Answer

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

Разберём алгоритм пошагово:

1. Функция `f(n)` переводит число $n$ в троичную систему счисления.
2. Для каждого числа $N$ от 1 до некоторого предела:
   - получаем его троичное представление;
   - если $N$ делится на 3, дописываем три последние цифры троичной записи;
   - если остаток от деления на 3 ненулевой, умножаем остаток на 3, переводим в троичную систему и дописываем;
   - переводим полученную троичную строку обратно в десятичное число;
   - если результат больше 150, добавляем $N$ в множество кандидатов.
3. Выводим минимальное значение из найденных.

```python
def f(n):
    s = ''
    while n > 0:
        s = str(n % 3) + s
        n //= 3
    return s

c = set()
for n in range(1, 100):
    s = f(n)
    if n % 3 == 0:
        s = s + s[-3:]
    else:
        s = s + f((n % 3) * 3)
    r = int(s, 3)
    if r > 150:
        c.add(n)

print(min(c))
```

Проверим на примере $N = 9$:
- Троичная запись: $9_{10} = 100_3$
- $9$ кратно 3, поэтому дописываем три последние цифры: $100 + 100 = 100100_3$
- Переводим в десятичную: $1 \cdot 3^5 + 0 \cdot 3^4 + 0 \cdot 3^3 + 1 \cdot 3^2 + 0 \cdot 3^1 + 0 \cdot 3^0 = 243 + 9 = 252$
- $252 > 150$ ✓

Для $N = 8$:
- Троичная запись: $8_{10} = 22_3$
- $8 \mod 3 = 2$, поэтому вычисляем $f(2 \cdot 3) = f(6) = 20_3$
- Дописываем: $22 + 20 = 2220_3$
- Переводим: $2 \cdot 3^3 + 2 \cdot 3^2 + 2 \cdot 3^1 + 0 = 54 + 18 + 6 = 78$
- $78 
ot> 150$ ✗

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

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