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