(В. Лашин) На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 5, то к этой записи справа дописываются две последние троичные цифры;
б) если число N на 5 не делится, то вычисляется произведение натуральных цифр полученной троичной записи, это произведение умножается на 2, переводится в троичную систему счисления и дописывается в начало числа.
Полученная таким образом запись является троичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 2010 = 2023 результатом является число 202023 = 18210, а для исходного числа 1910 = 2013 это число 112013 = 12710
Укажите минимальное нечётное число R, большее 405, которое может быть получено с помощью описанного алгоритма.
В ответе запишите это число в десятичной системе счисления.
Решение
🔹 Шаг 1. Функция f — троичная запись
# функция f — троичная запись
def f(n):
s = ''
while n:
n, r = divmod(n, 3)
s = str(r) + s
return s
📌 Результат: функция f переводит число в троичную запись.
🔹 Шаг 2. Перебор чисел и троичная запись
# перебор чисел и троичная запись
def f(n):
s = ''
while n:
n, r = divmod(n, 3)
s = str(r) + s
return s
for n in range(1, 20):
R = f(n)
print(n, '→', R)
📌 Результат: 1 → 1, 2 → 2, 3 → 10, 19 → 201 и т.д.
🔹 Шаг 3. Проверка делимости на 5
# проверка делимости на 5
def f(n):
s = ''
while n:
n, r = divmod(n, 3)
s = str(r) + s
return s
for n in range(1, 20):
R = f(n)
if n % 5 == 0:
print(n, R, 'делится на 5')
else:
print(n, R, 'НЕ делится на 5')
📌 Результат: 1 1 НЕ делится на 5, 2 2 НЕ делится на 5, 3 10 НЕ делится на 5, 19 201 НЕ делится на 5 и т.д.
🔹 Шаг 4. Изменение троичной строки
# изменение троичной строки
def f(n):
s = ''
while n:
n, r = divmod(n, 3)
s = str(r) + s
return s
from math import prod
for n in range(1, 20):
R = f(n)
if n % 5 == 0:
R = R + R[-2:]
print(n, '→', R, '(приписали последние 2 цифры)')
else:
mul = prod(int(i) for i in R) * 2
R = f(mul) + R
print(n, '→', R, '(дописали произведение слева)')
📌 Результат: 1 → 21 (дописали произведение слева), 2 → 112 (дописали произведение слева), 3 → 10 (дописали произведение слева), 19 → 201 (дописали произведение слева) и т.д.
🔹 Шаг 5. Поиск минимального нечётного R больше 405
Цель: собрать всё вместе и понять задачу целиком.
from math import prod
def f(n): # перевод в троичную систему (строка)
s = ''
while n:
n, r = divmod(n, 3)
s += str(r)
return s[::-1]
ans = 10**9
for N in range(1, 500): # перебор исходных чисел
R = f(N)
if N % 5 == 0:
# а) дописать справа 2 последние троичные цифры
R += R[-2:]
else:
# б) в начало — произведение цифр, умноженное на 2
mul = prod(int(i) for i in R) * 2
R = f(mul) + R
R = int(R, 3)
if R > 405 and R % 2 and R != N: # нечётное R; без «неизменившихся» N
ans = min(ans, R)
print(ans)
📌 Результат: минимальное нечётное R, большее 405. Ответ: 455.
