ЕГЭ информатика 5-е задание на питоне

Question

ЕГЭ информатика 5-е задание на питоне

Диана Абрамова Ученик (162), закрыт 1 год назад

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится пятеричная запись числа N.
2. Запись «переворачивается», то есть читается справа налево. Если при этом появляются ведущие нули, они отбрасываются.
3. Результат R вычисляется как модуль разности перевернутого и исходного чисел.
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, равное 100 P.S(100 в десятичной системе)
.

Answer 1

Для начала, обращаем внимание, что 100 = 400₅, и поскольку две последних цифры - нули, первая цифра исходного числа равна последней, а вторая - предпоследней, иначе мы эти нули в разности не получим.
Для трёх-, четырёх- и пяти- значных чисел разности будут равны нулю, т.к. по приведённому выше условию они могут быть только палиндромами (их запись в прямом порядке равна записи в обратном порядке).

Самое малое число, на котором мы получаем ненулевую разность под модулем, - шестизначное, т.к. в нём есть две средних цифры, на которые нет ограничения их равенства между собой, и значит, мы впервые получаем ненулевую разность.

 [abcdba] = a × 3125 + b × 625 + c × 125 + d × 25 + b × 5 + a
[abdcba] = a × 3125 + b × 625 + d × 125 + c × 25 + b × 5 + a
|[abcdba] - [abdcba]| = |(c - d) × (125 - 25)| = 100
|c - d| = 1
1 ≤ a < 5
0 ≤ b, c, d < 5

Поскольку нам нужно наименьшее число, берём наименьшие цифры под условия, минимизируя в первую очередь старшие разряды:

 a = 1    (старший разряд не может быть нулём)
b = 0    (эти спокойно могут быть нулями)
c = 0    (из пар 10 и 01 выбираем с меньшим значением более старшего разряда)
d = 1

Итого, пятеричное число:

 100101₅

А в десятичном виде:

 1 × 3125 + 1 × 25 + 1 = 3151

P.S. И естественно, никакой Питон здесь не нужен, задача решается ручкой на бумажке.

Answer 2

Для решения задачи можно реализовать алгоритм в обратном порядке:

Найти все числа, разность между которыми равна 100, в десятичной системе.
Проверить каждое найденное число, является ли оно результатом обработки описанного алгоритма.
Найти минимальное число среди найденных результатов.
Рассмотрим первый этап алгоритма:

Переведем число 100 в пятеричную систему исчисления: 100(dec) = 400(base5)
Рассмотрим перевернутое число: 004(base5). Ведущие нули отбрасываются, поэтому получаем 4(base5).
Вычислим модуль разности 400(base5) - 4(base5) = 396(base5).
Переведем результат обратно в десятичную систему исчисления: 396(base5) = 71(dec).
Теперь проверим, является ли полученное число 71 результатом обработки описанного алгоритма:

Переведем число 71 в пятеричную систему исчисления: 71(dec) = 341(base5).
Рассмотрим перевернутое число: 143(base5). Ведущие нули отбрасываются, поэтому получаем 143(base5).
Вычислим модуль разности 341(base5) - 143(base5) = 198(base5).
Переведем результат обратно в десятичную систему исчисления: 198(base5) = 53(dec).
Таким образом, минимальное число, после обработки которого с помощью описанного алгоритма получается число 71, равное 100, будет 53.

Answer 3

 def find_min_N(): 
    N = 1  # Начинаем с числа 1 
    convert_string = "0123456789ABCDEF"  # Строка для преобразования числа в другую систему счисления 
    while True:  # Бесконечный цикл, который продолжается, пока не будет найдено подходящее число 
        N_base_5 = ""  # Строка для хранения числа N в пятеричной системе счисления 
        temp = N  # Временная переменная для хранения числа N 
        while temp > 0:  # Цикл для преобразования числа N в пятеричную систему счисления 
            N_base_5 = convert_string[temp % 5] + N_base_5  # Добавляем остаток от деления на 5 к строке N_base_5 
            temp //= 5  # Делим temp на 5 
        reversed_N = int(N_base_5[::-1], 5)  # Переворачиваем число и преобразуем его обратно в десятичную систему счисления 
        R = abs(reversed_N - int(N_base_5, 5))  # Вычисляем модуль разности между перевернутым числом и исходным числом 
        if R == 100:  # Если R равно 100, возвращаем N 
            return N # Передаем значение N в функцию find_min_N 
        N += 1  # Увеличиваем N на 1 
 
print(find_min_N())  # Выводим результат функции find_min_N