Условие: КЕГЭ № 4869 (Уровень: Сложный)
• Статья подготовлена командой itpy
• Полный разбор задачи в Notion
Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:
1. Строится двоичная запись числа N.
2. Вычисляется количество единиц, стоящих на чётных местах в двоичной записи числа N без ведущих нулей, и количество нулей, стоящих на нечётных местах. Места отсчитываются слева направо (от старших разрядов к младшим, начиная с единицы).
3. Результатом работы алгоритма становится модуль разности полученных двух чисел.
Пример. Дано число N = 39. Алгоритм работает следующим образом:
1. Строится двоичная запись: 3910 = 1001112
2. Выделяем единицы на чётных и нули на нечётных местах: 100111
На чётных местах стоят две единицы, на нечётных – один ноль.
3. Модуль разности равен 1
Результат работы алгоритма R = 1
При каком наименьшем N в результате работы алгоритма получится R = 5?
Решение через Python и комментарии к нему:
Комментарии к коду решения:
- for n in range(2, 10000): - Просто пробегаем большой диапазон натуральных чисел.
- s = bin(n)[2:] - Преобразование числа n в двоичное представление и удаление префикса '0b'.
- chet1 = [x for x in s[1::2] if x == '1'] - Формирование списка всех '1' на четных позициях в строке s.
- nechet0 = [x for x in s[0::2] if x == '0'] - Формирование списка всех '0' на нечетных позициях в строке s.
- r = abs(len(chet1) - len(nechet0)) - Вычисляем разницу между количеством '1' на четных и '0' на нечетных позициях.
- if r == 5: - Проверяем: если разница равна 5.
- print(n) - Вывод число n.
- break - Прерываем цикл, так как нам нужно наименьшее, а диапазон чисел изначально упорядочен по возрастанию.
Это еще один вариант решения, считаю его более универсальным. Оставляю для самоизучения.