Question

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

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

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

Укажите максимальное число $R$, не превышающее 173, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.

Accepted Answer

162

Answer

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

Алгоритм работает так:
1. Для каждого числа $N$ вычислим его троичное представление.
2. В зависимости от остатка $N$ при делении на 3 дополним троичную запись:
   - если остаток 0, добавим две последние цифры исходной записи;
   - если остаток не равен 0, вычислим остаток, умножим на 5, переведём в троичную систему и добавим.
3. Полученную строку интерпретируем как троичное число и переводим в десятичную систему.
4. Если результат не превышает 173, добавим его в множество.
5. Найдём максимум из полученного множества.

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

results = set()

for n in range(1, 100):
    s = to_base3(n)
    
    if n % 3 == 0:
        s = s + s[-2:]
    else:
        remainder = (n % 3) * 5
        s = s + to_base3(remainder)
    
    r = int(s, 3)
    
    if r <= 173:
        results.add(r)

print(max(results))
```

Проверим логику на примере:
- $N = 51$: троичная запись — `1220`, остаток $51 \bmod 3 = 0$, добавляем `20`, получаем `122020` в троичной системе, что равно $1 \cdot 243 + 2 \cdot 81 + 2 \cdot 27 + 0 \cdot 9 + 2 \cdot 3 + 0 = 243 + 162 + 54 + 6 = 465 > 173$ — не подходит.
- $N = 54$: троичная запись — `2000`, остаток $54 \bmod 3 = 0$, добавляем `00`, получаем `200000` в троичной системе, что равно $2 \cdot 243 = 486 > 173$ — не подходит.
- $N = 18$: троичная запись — `200`, остаток $18 \bmod 3 = 0$, добавляем `00`, получаем `20000` в троичной системе, что равно $2 \cdot 81 = 162 \leq 173$ — подходит.

Программа перебирает все числа от 1 до 99, применяет преобразование и находит максимальное значение $R$, не превышающее 173.

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