Пример e501

Условие

Источник задания: Основная волна 2023

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

Строится двоичная запись числа N.
Далее эта запись обрабатывается по следующему правилу:
- если число N делится на 3, то в этой записи дописываются справа три последние двоичные цифры;
- если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа R.
Результат переводится в десятичную систему счисления и выводится на экран.

Например, для исходного числа 12 = 1100₂ результатом является число 1100100₂ = 100, а для исходного числа 4 = 100₂ результатом является число 10011₂ = 19.

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

Решение

Напишем программу перебора для поиска ответа.

Для начала определим диапазон для значений переменной N. Так как число R не должно превосходить 170, то для N нет смысла брать верхнюю границу диапазона больше чем 170. Начать проверку можно с числа 4.

Правую границу можно уменьшить, если обратить внимание на то, что в R записанном в двоичной системе счисления, минимум на 2 разряда больше, чем в исходном числе N. Так как остаток от деления на 3 это числа 1 или 2. Умножая 1 на 3 — получим в двоичной системе счисления число 11₂, а 2 на 3 — число 6, соответственно в двоичной системе счисления 110₂.

Отсюда следует, что можно перевести число 170 в двоичную систему счисления — 10101010₂, откинуть 2 разряда справа, перевести обратно в десятичную, и на всякий случай увеличить на 1. Получим правую границу равную 43.

Левой границей диапазона стало число 4, так как 3 кратно 3, и по алгоритму к нему нужно дописать 3 последние цифры двоичной записи, но 3 в двоичной системе счисления равно 11₂. Чтобы не противоречить алгоритму, начинаем с числа, в котором точно есть 3 цифры в двоичной записи

Перейдем к написанию алгоритма. Объявим переменную max_R, в которую будем записывать максимальное значение результатов выполнения алгоритма. Затем в цикле for выполним все действия алгоритма преобразования числа, для начала построим двоичную запись для числа N. Сделаем срез со второго символа, чтобы в R записались только цифры (0b не нужно).

            #начало фрагмента
max_R = 0
for i in range(4, 171):
    R = int(i)[2:]
#конец фрагмента

Дальше в зависимости от кратности N числу три изменим число, согласно алгоритму.

Если число кратно трем, то допишем к двоичной записи числа три последние цифры. Для этого сделаем срез [-3:]. Если число некратно, то найдем остаток от деления на три — i % 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