ЕГЭ · ЗАДАНИЕ 5
Алгоритмы обработки чисел · №20884
(О. Лысенков) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр троичной записи кратна 3, то все нули в записи меняются на 1, а все 1 меняются на 0, после к числу приписывается 10 слева;
б) если сумма цифр троичной записи не кратна 3, то к записи справа приписывается 101, после первые 2 разряда меняются на 22, разряды нумеруются слева направо, начиная с 1.
Полученная таким образом запись является троичной записью искомого числа R.
Укажите минимальное число N, для которого результатом работы алгоритма является наименьшее число R, превышающее 314.
В ответе это число запишите в десятичной системе счисления.''
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 76
def cc(n):
s = ''
while n != 0:
s = str(n % 3 ) + s
n //= 3
return s
def f(n):
s = cc(n)
sum_digits = s.count('1') + s.count('2') * 2
if sum_digits % 3 == 0:
s = s.replace('1','*').replace('0','1').replace('*','0')
s = '10' + s
else:
s += '101'
s = '22' + s[2:]
return int(s,3)
mi = float('inf')
a = []
for i in range(1,1000):
if f(i) > 314:
a.append([f(i),i])
a.sort()
print(a[0][1])