Задача #3096
Алгоритмы
(О. Лысенков) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится четверичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если сумма цифр четверичной записи кратна 3, то все нули в записи меняются на 2, а все 2 меняются на нули, после к числу приписывается 32 слева;
б) если сумма цифр четверичной записи не кратна 3, то к записи справа приписывается 33, после второй и третий разряд, полученной записи, меняются на 1 и 0 соответственно, разряды нумеруются слева направо, начиная с 1.
Полученная таким образом запись является четверичной записью искомого числа R.
Укажите максимальное число N, для которого результатом работы алгоритма является наименьшее число R, превышающее 320.
В ответе это число запишите в десятичной системе счисления.
Решение
Ответ
def cc(n):
s = ''
while n != 0:
s = str(n % 4) + s
n //= 4
return s
def f(n):
s = cc(n)
sum_digits = sum(map(int,list(s)))
if sum_digits % 3 == 0:
s = s.replace('0','*').replace('2','0').replace('*','2')
s = '32' + s
else:
s += '33'
s = s[0] + '10' + s[3:]
return int(s,4)
mi = float('inf')
a = []
for i in range(1,100000):
if f(i) > 320:
a.append([f(i),-i])
a.sort()
print(abs(a[0][1]))