5.02 Запись числа в другой системе счисления

В данной задаче нам необходимо реализовать алгоритм преобразования натурального числа N в новое число R на основе четверичной записи N. Для этого мы сначала пишем собственную функцию f, которая переводит десятичное число n в систему счисления с основанием osn (в нашем случае — в четверичную систему). Функция последовательно делит число на основание системы счисления, записывая остатки от деления в строку в обратном порядке, после чего переворачивает строку, получая корректную запись числа.

Далее, в основном цикле, перебирая числа N от 1 до 199, мы переводим каждое число в четверичную запись с помощью функции f. После этого необходимо найти произведение всех цифр этой записи, исключая нули, так как они не влияют на произведение, а также не могут повлиять на кратность произведения числу 3. Для этого мы используем функцию map, которая преобразует строку цифр в список целых чисел, затем в цикле умножаем эти цифры, пропуская нули. После вычисления произведения проверяем, делится ли оно на 3 без остатка — это и есть проверка кратности 3. В зависимости от результата мы либо дописываем в конец четверичной записи ’21’ (если произведение кратно 3), либо ’12’ (если нет). Получившуюся строку далее переводим обратно из четверичной системы в десятичное число, чтобы сравнивать с ограничением 280. Если число R не превышает 280, мы добавляем его в множество, чтобы избежать повторений. В конце выводим максимальное значение из этого множества, которое и будет искомым ответом.

def f(n, osn):  # Функция перевода числа n в систему счисления с основанием osn
    s = ’’  # Инициализируем пустую строку для записи цифр числа в новой системе счисления
    while n > 0:
        s += str(n % osn)  # Добавляем в строку остаток от деления числа n на основание системы счисления
        n //= osn  # Целочисленно делим число n на основание системы счисления, чтобы перейти к следующей цифре
    s = s[::-1]  # Переворачиваем строку, так как цифры добавлялись в обратном порядке
    return s  # Возвращаем полученную строку — корректное представление числа в новой системе счисления

a = set()  # Создаем множество для хранения уникальных значений R, которые удовлетворяют условию
for n in range(1, 200):  # Перебираем числа N от 1 до 199 включительно
    s = f(n, 4)  # Переводим число n в четверичную систему счисления с помощью функции f

    k = map(int, s)  # Преобразуем строку s в последовательность целых чисел — цифр четверичной записи
    mult = 1  # Инициализируем переменную для произведения цифр, отличных от нуля

    for i in k:  # Для каждой цифры i из последовательности
        if i != 0:  # Если цифра не равна нулю, умножаем текущее произведение на эту цифру
            mult *= i

    if mult % 3 == 0:  # Проверяем, делится ли произведение на 3 без остатка
        s += ’21’  # Если делится, дописываем к записи справа ’21’
    if mult % 3 != 0:  # Если не делится
        s += ’12’  # Дописываем к записи справа ’12’

    r = int(s, 4)  # Переводим полученную четверичную запись обратно в десятичное число для сравнения

    if r <= 280:  # Проверяем, что число R не больше 280
        a.add(r)  # Добавляем число R во множество для хранения уникальных значений

print(max(a))  # Выводим максимальное число R, удовлетворяющее условию задачи