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

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

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

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

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

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

#Эффективный алгоритм
file = open(’27B_1__3shr0.txt’) #открытие файла
n = int(file.readline()) #считываем первое число - количество чисел в файле
div = 88 # наш делитель
mx = [0]*div # список, в котором будет храниться максимальное число под каждым остатком при делении на 88
mx_sum = 0 # максимальная сумма пары
for i in range(n): # проход по всему файлу
    x = int(file.readline()) # считываем текущее число
    need_ost = (div - x % div) % div # определяем необходимый остаток для второго числа чтобы в итоге получилась пара кратная 88
    if x < mx[need_ost]: # если первое число в паре больше второго
        mx_sum = max(mx_sum,x+mx[need_ost]) # то обновляем максимальную сумму
    mx[x % div] = max(mx[x % div],x) # обновляем максимальное число под определенным остатком, сравнивая текущее число с тем, что было записано в ячейке ранее.
print(mx_sum) # вывод ответа

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