КЕГЭ № 4869 (Уровень: Сложный)

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:

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

2. Вычисляется количество единиц, стоящих на чётных местах в двоичной записи числа N без ведущих нулей, и количество нулей, стоящих на нечётных местах. Места отсчитываются слева направо (от старших разрядов к младшим, начиная с единицы).

3. Результатом работы алгоритма становится модуль разности полученных двух чисел.

Пример. Дано число N = 39. Алгоритм работает следующим образом:

1. Строится двоичная запись: 3910 = 1001112

2. Выделяем единицы на чётных и нули на нечётных местах: 100111

На чётных местах стоят две единицы, на нечётных – один ноль.

3. Модуль разности равен 1

Результат работы алгоритма R = 1

При каком наименьшем N в результате работы алгоритма получится R = 5?

Комментарии к коду решения:

1. for n in range(2, 10000): - Просто пробегаем большой диапазон натуральных чисел
2. s = bin(n)[2:] - Преобразование числа n в двоичное представление и удаление префикса '0b'.
3. chet1 = [x for x in s[1::2] if x == '1'] - Формирование списка всех '1' на четных позициях в строке s.
4. nechet0 = [x for x in s[0::2] if x == '0'] - Формирование списка всех '0' на нечетных позициях в строке s.
5. r = abs(len(chet1) - len(nechet0)) - Вычисляем разницу между количеством '1' на четных и '0' на нечетных позициях.
6. if r == 5: - Проверяем: если разница равна 5.
7. print(n) - Вывод число n.
8. break - Прерываем цикл, так как нам нужно наименьшее, а диапазон чисел изначально упорядочен по возрастанию.

for n in range(2, 10000):
    s = bin(n)[2:]

    chet1 = [x for x in s[1::2] if x == '1']
    nechet0 = [x for x in s[0::2] if x == '0']

    r = abs(len(chet1) - len(nechet0))
    if r == 5:
        print(n)
        break