Статья Автор: Деникина Н.В., Деникин А.В.

Повторная проверка чётности

Задача

Источник: ЕГЭ-2024

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

1. Строится двоичная запись числа N.

2. К этой записи дописываются справа ещё два разряда по следующему правилу:

а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.

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

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

Решение

После первого контрольного бита запись меняется. Второй бит вычисляем уже для неё, а не копируем первый.

Для N = 13 вычисли первый дописываемый бит. В ответ укажите только сам БИТ (0 или 1), а не число.

Проверить ответ

Решение с конца: работаем с разрядами

Ищем минимальное R > 123, которое действительно может получиться по алгоритму. Дважды считаем количество единиц: сначала в исходной записи, затем ещё раз после добавления первого контрольного бита.

Проверяем результаты по возрастанию:

Проверяем текущий результат Берём ближайший кандидат

Шаг 1 из 6

Решение текстом

Нужно найти минимальное значение R > 123. Поэтому начинаем проверку с ближайших чисел: 124, 125, 126, …

Их двоичные записи:

124 = 1111100₂
125 = 1111101₂
126 = 1111110₂

Удалим у каждого кандидата два последних разряда, которые были добавлены алгоритмом. Во всех трёх случаях останется:

11111₂ = 31.

В исходной записи пять единиц. Пять — нечётное число, поэтому первым дописывается бит 1:

11111 → 111111

Теперь в записи уже шесть единиц. Шесть — чётное число, поэтому вторым дописывается бит 0:

111111 → 1111110₂

Получилась запись числа 126. Поэтому 124 и 125 алгоритмом получить нельзя, а 126 — можно.

Ответ: 126.

Как ускорить — необязательно

Первый контрольный бит делает число единиц чётным, поэтому второй всегда равен 0. Значит, результат оканчивается на 00 или 10. После 123 достаточно проверить 124 и 126; 126 проходит.

Программное решение

Перебираем N, дважды пересчитываем сумму цифр и ищем минимум R > 123. N ≥ 100 даст R ≥ 400 и уже не улучшит 126.

В программе рассмотрим второй вариант поиска экстремума ответа. Заведем список R, в который будем добавлять подходящие ответы. Затем, используя функцию min(R), найдем ответ из найденных.

limit = 123            # R должен быть больше этой границы
R = []                 # R все возможные результаты будем добавдять в список
                       # Ответ найдем одной функцией min
for n in range(1, 100):
    s = bin(n)[2:]
    p = s.count("1") % 2
    s = s + str(p)
    p = s.count("1") % 2
    s = s + str(p)
    r = int(s, 2)
    if r > limit:
        R.append(r)
        
print(min(R))

Вывод программы

Совпало с разбором.

Получено R = 92. Восстанови N и проверь контрольные биты.

Проверить ответ

Не потеряй балл

Не подменяй чётность суммы цифр чётностью N.
Не копируй первый контрольный бит на второе место.

Печать