ЕГЭ · ЗАДАНИЕ 5
Алгоритмы обработки чисел · №1285
Натуральное N. Двоичная запись N дважды дополняется справа остатком от деления суммы её цифр на 2. Перед вторым дополнением сумма считается уже в изменённой записи. Найдите минимальное возможное R, превышающее 396. Ответ запишите в десятичной системе.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 402
Сначала постройте R для одного N по ветвям условия. В проверке используем r > 396; в список кладём r, потому что ответом требуется именно R. Затем берём минимум. В этом алгоритме R ≥ N. Найден кандидат R = 402; при N ≥ 1000 получим R ≥ 1000 > 402. Поэтому больший N не улучшит ответ; внутри диапазона проверяем все результаты, не прерываясь на первом.
def get_r(n):
s = bin(n)[2:]
for _ in range(2):
s += str(s.count('1') % 2)
return int(s, 2)
answers = []
for n in range(1, 1000):
r = get_r(n)
if r > 396:
answers.append(r)
print(min(answers))