ЕГЭ Информатика 2022: Задача 5

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

Строится двоичная запись числа n.
К этой записи дописываются справа ещё два разряда по следующему правилу:
- 1. Складываются все цифры двоичной записи числа n.
- 1. Остаток от деления суммы на 2 дописывается в конец числа справа.
- 1. Над получившейся записью производится те же действия (пункты a и b).
Полученная запись является двоичной записью результирующего числа p.

Задача: Указать наименьшее число n, для которого результат работы алгоритма (p) больше 77. Ответ записать в десятичной системе счисления.

Решение

Один из подходов к решению задачи — метод перебора. Рассмотрим число 78 (первое число больше 77). Его двоичная запись — 1001110. Количество единиц — 5 (нечётное). Добавляем 1: 10011101. Суммируем цифры: 1+0+0+1+1+1+0+1 = 5. Остаток от деления на 2: 1. Добавляем 1: 100111011. Полученное число — 100111011₂. Перевод в десятичную систему: 307. Число 307 > 77. Следовательно, число 78 не подходит.

Вместо ручного перебора напишем программу на Python:

for i in range(1, 101):
    n = bin(i)[2:]
    for _ in range(2):
        count_ones = n.count('1')
        n += str(count_ones % 2)
    p = int(n, 2)
    if p > 77:
        print(f"n = {i}, p = {p}")
        break

Программа выведет: n = 19, p = 131. Наименьшее число n, удовлетворяющее условию, равно 19.

ЕГЭ Информатика 2022: Задача 5 — решение

Решение