Задача #1485
Алгоритмы
(М. Ишимов) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр троичной записи числа N делится на 4, то слева дописывается «1», а затем из полученной записи удаляются два правых разряда;
б) если сумма цифр троичной записи числа N на 4 не делится, то остаток от деления этой суммы на 4 сначала умножается на 3, а затем переводится в троичную запись и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа 11 = 1023 результатом является число 1021003 = 306, а для исходного числа 16 = 1213 результатом является число 113 = 4.
Укажите минимальное число R, большее 353, которое может получиться с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.
Решение
Ответ
Видео по задаче
def tr(x):
b = ''
while x:
b = str(x % 3) + b
x //= 3
return b
def sm(el):
return sum(int(c) for c in el)
res = []
for n in range(1, 100000):
b = tr(n)
if sm(b) % 4 == 0:
b = '1' + b
b = b[:-2]
else:
b += tr( sm(b) % 4 * 3 )
r = int(b, 3)
if r > 353:
res += [r]
print(min(res))