ЕГЭ · ЗАДАНИЕ 5
Алгоритмы обработки чисел · №21700
Натуральное N. При N > 2 строится троичная запись N. Если N кратно 3, справа дописывают последние две троичные цифры. Иначе справа дописывают троичную запись 3·(N mod 3). Полученную запись переводят в десятичное R. Найдите максимальное N при R ≤ 150. Ответ запишите в десятичной системе.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 16
Сначала постройте R для одного N по ветвям условия. В проверке используем r <= 150; в список кладём n, потому что ответом требуется именно N. Затем берём максимум. Алгоритм дописывает цифры и даёт R ≥ N. При N ≥ 151 верхняя граница на R уже невыполнима.
def to_base(n, base):
s = ''
while n:
s = str(n % base) + s
n //= base
return s or '0'
def get_r(n):
s = to_base(n, 3)
s += s[-2:] if n % 3 == 0 else to_base(3 * (n % 3), 3)
return int(s, 3)
answers = []
for n in range(3, 151):
r = get_r(n)
if r <= 150:
answers.append(n)
print(max(answers))