Разборы · ЕГЭ, задание 5

Задание 5 ЕГЭ по информатике: алгоритм построения числа

Что проверяет задание

Алгоритм получает натуральное число N, переводит его в двоичную (иногда троичную) запись, дописывает или меняет разряды по правилам и выдаёт новое число R. Нужно найти наименьшее N или наименьшее R с заданным свойством. 1 балл.

Что нужно знать

bin(n)[2:] — двоичная запись числа без префикса 0b; int(s, 2) — обратный перевод.
Сумма цифр двоичной записи — s.count("1"); чётность числа — n % 2.
Дописать цифру справа к двоичной записи — всё равно что умножить на 2 и прибавить цифру.

Как решать

Напишите функцию, которая строит R по N строго по тексту условия.
Проверьте её на примере из условия — там всегда есть пара «N → R». Это ловит почти все ошибки.
Переберите N в большом диапазоне и выберите нужное значение.

Пример из демоверсии 2027

Строится двоичная запись N. Если N чётное, к записи справа и слева дописывается по две единицы; если нечётное — справа дописываются два нуля, а слева единица. Получившаяся запись — это R. Например, 13 = 1101₂ → 1110100₂ = 116, а 6 = 110₂ → 1111011₂ = 123. Укажите наименьшее R, превышающее 95.

def R(n):
    b = bin(n)[2:]
    if n % 2 == 0:
        b = "11" + b + "11"
    else:
        b = "1" + b + "00"
    return int(b, 2)

print(R(13), R(6))                                   # 116 123 — как в условии
print(min(R(n) for n in range(1, 1000) if R(n) > 95))

Программа выводит 100: это 1100100₂, получается из N = 9 = 1001₂ (нечётное: единица слева, два нуля справа).

Диапазон перебора берите с запасом: R растёт вместе с N, поэтому нескольких сотен чисел достаточно. Если сомневаетесь, увеличьте диапазон и убедитесь, что ответ не изменился.

Типичные ошибки

Путают, что ищут: наименьшее N или наименьшее R.
Путают «превышающее 95» (> 95) и «не меньше 95» (≥ 95).
Проверяют чётность у двоичной строки, а не у числа, или дописывают разряды не с той стороны. Пример из условия сразу покажет такую ошибку.

Потренироваться: задание 5 новые варианты с проверкой ответа