Условие
Источник задания: Основная волна 2023
- Строится двоичная запись числа N.
- Далее эта запись обрабатывается по следующему правилу:
- если число N делится на 3, то в этой записи дописываются справа три последние двоичные цифры;
- если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
- Результат переводится в десятичную систему счисления и выводится на экран.
Решение
Напишем программу перебора для поиска ответа.
Для начала определим диапазон для значений переменной N. Так как число R не должно превосходить 170, то для N нет смысла брать верхнюю границу диапазона больше чем 170. Начать проверку можно с числа 4.
Правую границу можно уменьшить, если обратить внимание на то, что в R записанном в двоичной системе счисления, минимум на 2 разряда больше, чем в исходном числе N. Так как остаток от деления на 3 это числа 1 или 2. Умножая 1 на 3 — получим в двоичной системе счисления число 112, а 2 на 3 — число 6, соответственно в двоичной системе счисления 1102.
Отсюда следует, что можно перевести число 170 в двоичную систему счисления — 101010102, откинуть 2 разряда справа, перевести обратно в десятичную, и на всякий случай увеличить на 1. Получим правую границу равную 43.
Левой границей диапазона стало число 4, так как 3 кратно 3, и по алгоритму к нему нужно дописать 3 последние цифры двоичной записи, но 3 в двоичной системе счисления равно 112. Чтобы не противоречить алгоритму, начинаем с числа, в котором точно есть 3 цифры в двоичной записи
Перейдем к написанию алгоритма. Объявим переменную max_R, в которую будем записывать максимальное значение результатов выполнения алгоритма. Затем в цикле for выполним все действия алгоритма преобразования числа, для начала построим двоичную запись для числа N. Сделаем срез со второго символа, чтобы в R записались только цифры (0b не нужно).
max_R = 0
for i in range(4, 171):
R = int(i)[2:]
Дальше в зависимости от кратности N числу 3 изменим число, согласно алгоритму.
Если число кратно 3, то допишем к двоичной записи числа три последние цифры. Для этого сделаем срез [-3:]. Если число некратно, то найдем остаток от деления на 3 — i % 3. Затем умножим его на 3. Переведем в двоичную системы счисления.
if i % 3 == 0:
R += R[-3:]
else:
R += bin((i % 3) * 3)[2:]
Оператор сложения с присваиванием += добавляет значение правого операнда к переменной и присваивает переменной результат.
Переведем полученное число в десятичную систему счисления.
R = int(R, 2)
Каждый полученный результат сравним с максимальным.
if R <= 170:
max_R = max(max_R, R)
Функция max() возвращает наибольшее значение элемента итерируемого объекта или самое большое из двух или более переданных позиционных аргументов.
Выведем результат на экран.
print(max_R)
Листинг программы
max_R = 0
for i in range(4, 43):
R = bin(i)[2:]
if i % 3 == 0:
R += R[-3:]
else:
R += bin((i % 3) * 3)[2:]
R = int(R, 2)
if R <= 170:
max_R = max(max_R, R)
print(max_R)
Ответ
166