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