В чем ошибка? Задача из ЕГЭ на Python

Question

В чем заключается ошибка в коде? На вход алгоритма подается натуральное число N > 1. Алгоритм строит по нему новое число R следующим образом.

Строится двоичная запись числа N.
Из полученной записи убирается старшая (левая) единица.
Далее эта запись обрабатывается по следующему правилу:
1. если в полученной записи количество единиц четное, то слева дописывается 10;
2. если количество единиц нечётное, слева дописывается 1, справа 0.

Полученная таким образом запись является двоичной записью искомого числа R.

Например,

для исходного числа 4 = 100₂ результатом будет являться число 8 = 1000₂, а для исходного числа 6 = 110₂ результатом будет являться число 12 = 1100₂.

Укажите максимальное число R, меньшее 450, которое может являться результатом работы алгоритма. В ответе запишите это число в десятичной системе счисления.

Ответ 444, выводит 382

def to_two(n):
    s = ""
    while n > 0:
        s = str(n % 2) + s
        n //= 2
    return s

for n in range(100000):
    k1 = to_two(n)
    k1 = k1[1:]  
    if k1.count("1") % 2 == 0:
        k1 = "10" + k1
    else:
        k1 = "1" + k1 + "0"
    if int(k1, 2) < 450:
        ans = int(k1, 2)
print(ans)

Answer 1

А у Вас был ответ 444, но в ходе дальнейшего выполнения цикла он "затерся" последним успешным сравнением if int(k1, 2) < 450. Надо перед началом цикла присвоить ans=0, а потом не запоминать ответы, если они меньше "предыдущего" ans.

Answer 2

Я бы обходил результирующие числа задом наперед, поскольку нужно найти наибольшее. А входящие числа можно вообще не рассматривать.

for i in range(449, -1, -1):
    b = f'{i:b}'
    if b[:2] == '10' and b[3:].count('1') % 2 == 0 or b[0] + b[-1] == '10' and b[1:-1].count('1') % 2:
        print(i)
        break

БЛОГ НА HUSL

В чем ошибка? Задача из ЕГЭ на Python

Ответы (2 шт):