Задача к ЕГЭ по информатике на тему «Макс/мин, кол-во пар, сумма/разность кратна/не кратна» №9

Имеется набор данных из N  целых чисел. Рассматриваются все пары различных элементов последовательности такие что 1 ≤ i < j ≤ N  и ai > aj  » class=»math» src=»/images/inform/quest/quest-6067-3.svg» width=»auto»>, при этом оба числа должны быть больше 45. Необходимо определить минимальную сумму среди всех пар, которая будет кратна 63. </p>
<p class= Входные данные: Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000).  Каждая из следующих N строк содержит одно натуральное число, не превышающее 10000.

В ответе укажите два числа через пробел: сначала значение для файла А, затем для файла B.

Идея эффективного решения:

Идея решения заключается в том, чтобы под каждым остатком при делении на 63 собрать минимальное число бОльшее 45 для того чтобы в итоге получить минимальную сумму пары. Сумма пары кратна 63 в том случае, когда сумма остатков при делении на 63 пары чисел кратна 63. Проходясь по файлу,мы сначала будем проверять, что число бОльше 45,а затем мы будем искать для текущего числа подбирать такое число, с которым в сумме с ним будет кратна 63. Число, которое мы считываем на текущей итерации всегда будет вторым в паре (j индекс). Числа, которые уже записаны в списке — всегда будут первыми в паре(i индекс). Не трудно определить какой остаток нужен для второго числа при делении, зная, остаток первого числа, для этого можно использовать формулу: (D — x % D) % D , где D — это 63, а x — первое число пары.

f = open(’27A_3.txt’) #открытие файла
n = int(f.readline()) #считываем первое число - количество чисел в файле
arr = list(map(int, f.read().split())) #список, в котором будут записаны все числа файла
mn = 10000000 #минимальная сумма пары
for i in range(n-1): #перебор для первого числа пары
    for j in range(i+1, n):#перебор для второго числа пары
        if arr[i] > arr[j] and arr[i] + arr[j] < mn and (arr[i] + arr[j]) % 63 == 0 and arr[i] > 45 and arr[j] > 45: #проверка по условию
            mn = arr[i] + arr[j] # обновление минимальной суммы
print(mn) #вывод ответа.

#Эффективный алгоритм
file = open(’27B_3__3shrm.txt’) #открытие файла
n = int(file.readline()) #считываем первое число - количество чисел в файле
div = 63 # наш делитель
mn = [10**10]*div # список, в котором будет храниться минимальное число под каждым остатком при делении на 63
mn_sum = 10**10 # минимальная сумма пары
for i in range(n): # проход по всему файлу
    x = int(file.readline()) # считываем текущее число
    need_ost = (div - x % div) % div # определяем необходимый остаток для второго числа чтобы в итоге получилась пара кратная 63
    if x > mn[need_ost] and x > 45: # если второе число в паре больше первого, а также, что число больше 45
        mn_sum = min(mn_sum,x+mn[need_ost]) # то обновляем минимальную сумму
    if x > 45: # если текущее число больше 45
        mn[x % div] = min(mn[x % div],x) # обновляем минимальное число под определенным остатком, сравнивая текущее число с тем, что было записано в ячейке ранее.
print(mn_sum) # вывод ответа

Ответ: 189 126
Оцените статью
Я решу все!