Статья Автор: Деникина Н.В., Деникин А.В.

Троичная система счисления

Задача

Источник: ЕГКР-2025.

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

Строится троичная запись числа N.

Далее эта запись обрабатывается по следующему правилу:

a) если число N делится на 3, то к этой записи дописываются две последние троичные цифры;

б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в троичную систему и дописывается в конец числа.

Полученная таким образом запись является троичной записью искомого числа R. Например, для исходного числа 6 = 20₃ результатом является число 2020₃ = 60, а для исходного числа 4 = 11₃ результатом является число 1110₃ = 39. Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число, не превышающее 150. В ответе запишите это число в десятичной системе счисления.

Решение

Во всех ветках добавляются две троичные цифры. Убери их у 150, получи кандидата N и выполни алгоритм. Достаточно R ≤ 150; равенство не требуется.

Выполни алгоритм для N = 7. Найди R.

Проверить ответ

Решение с конца: от границы к максимальному N

Ищем максимальное N, для которого результат алгоритма удовлетворяет условию R ≤ 150. Работаем с конца: сначала по границе оцениваем максимально возможную троичную запись N, затем проверяем её и следующий вход.

150 = 12120₃ → N ≤ 121₃ → N = 16 → R = 147

Решаем с конца Переводим верхнюю границу

Шаг 1 из 6

Решение текстом

Нужно найти максимальное N, для которого после выполнения алгоритма R ≤ 150.

Сначала переведём границу 150 в троичную систему:

150 = 12120₃.

В любой ветке алгоритма справа добавляются ровно две троичные цифры. Поэтому для оценки максимально возможного N убираем два последних разряда:

121 | 20

Получаем кандидат:

N = 121₃ = 16.

Теперь нельзя просто использовать снятый хвост 20. Реальный хвост нужно вычислить по алгоритму.

Остаток от деления 16 на 3 равен 1. Умножаем его на 3:

1 · 3 = 3 = 10₃.

Поэтому к записи N дописывается 10:

121 | 10 = 12110₃ = 147.

Получили 147 ≤ 150. Значит, N = 16 подходит.

Осталось доказать, что большего N быть не может. Следующее число:

17 = 122₃.

После работы алгоритма к его записи обязательно добавятся ещё две троичные цифры. Даже если заменить их минимально возможной двухразрядной записью 00, получим:

12200₃ = 153.

Уже 153 > 150. Поэтому N = 17 и любые большие N не подходят.

Ответ: 16.

Как ускорить — необязательно

Две добавленные троичные цифры означают, что результат не меньше записи N с двумя нулями справа. Для N = 17 это уже 12200₃ = 153 > 150. Значит, N ≤ 16; число 16 проверкой даёт 147.

Программное решение

Программа перебирает N и сохраняет наибольший вход, для которого результат не превышает 150. Это проверяет вывод N = 16.

Две троичные цифры означают R ≥ 9N. Поэтому проверяем N до 150 // 9 включительно.

def n3(x):       # функция перевода числа в троичную СС
    s = ""
    while x > 0:
        s = str(x % 3) + s
        x = x // 3
    return s


limit = 150            # R не превышает эту границу
best = 0
for n in range(3, limit // 9 + 1):
    x = n
    s = n3(n)
    if n % 3 == 0:
        tail = s[-2:]
    else:
        x = (n % 3) * 3
        tail = ""
        while x > 0:
            tail = str(x % 3) + tail
            x = x // 3
    r = int(s + tail, 3)
    if r <= limit:
        best = n
print(best)

Вывод программы

Совпало с разбором.

Алгоритм выдал R = 120. Восстанови N.

Проверить ответ

Не потеряй балл

Не выдавай границу N за ответ без проверки.
Не считай троичное 10 десятичной десяткой.

Печать