Задание 5. Информатика. ЕГЭ. Поляков-6576

(А. Богданов) Назовём битом чётности остаток от деления числа единиц двоичной записи на \(2.\) На вход алгоритма подаётся натуральное число \(N.\) Алгоритм строит по нему новое число \(R\) следующим образом:

1. Строится двоичная запись числа \(N.\)
2. Если число \(N\) четное, то к двоичному представлению слева дописывается \(1,\) а справа бит четности числа \(N;\) если число нечетное, то к двоичному представлению справа дописывается \(0\) и затем бит четности числа \(N.\)
3. Полученная таким образом запись является двоичной записью искомого числа \(R.\)

Например, для исходного числа \(12 = 1100_2\) результатом является число \(111000_2 = 56,\) а для исходного числа \(5 = 101_2\) результатом является число \(10100_2 = 20.\) Укажите число \(N,\) после обработки которого с помощью этого алгоритма получается минимальное число \(R,\) большее \(100.\)

def R(N):
    bn = f'{N:b}'
    parity_bit = str(bn.count('1') & 1)
    bn = bn + '0' if N & 1 else '1' + bn
    bn += parity_bit
    return int(bn, 2)

min_R = 10**100
ans = 0
for N in range(1, 100):
    tmp = R(N)
    if min_R > tmp > 100:
        ans = N
        min_R = tmp
print(ans)