27.05 Макс/мин, кол-во пар, сумма/разность кратна/не кратна
Ошибка.
Попробуйте повторить позже
На вход программы поступает последовательность из n целых чисел. Рассматриваются все пары элементов
последовательности 
и 
, такие что 
и 
(первый элемент пары больше второго; i и j — порядковые
номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, требуется определить
пару с максимальной суммой элементов, которая делится на 98. Если среди найденных пар максимальную сумму имеют
несколько, то нужно напечатать последнюю из них.
В первой строке входных данных задаётся количество чисел n (2 
n 
10000).
В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.
Пример входных данных:
6
11
3
80
100
18
59
Выходные данные для приведённого выше примера: 80 18
В ответе укажите четыре числа: сначала для файла А, затем для файла B.
Идея эффективного решения:
Идея решения заключается в том, чтобы под каждым остатком при делении на 98 собрать максимальное число для того чтобы в итоге получить максимальную сумму пары. Сумма пары кратна 98 в том случае, когда сумма остатков при делении на 88 пары чисел кратна 98. Проходясь по файлу, мы будем искать для текущего числа подбирать такое число, с которым в сумме с ним будет кратна 98. Число, которое мы считываем на текущей итераций всегда будет вторым в паре (j индекс). Числа, которые уже записаны в списке - всегда будут первыми в паре(i индекс). Не трудно определить какой остаток нужен для второго числа при делении, зная, остаток первого числа, для этого можно использовать формулу: (D - x % D) % D , где D - это 98, а x - первое число пары.
f = open(’27A__tcf4.txt’) #открытие файла n = int(f.readline()) #считываем первое число - количество чисел в файле arr = list(map(int, f.read().split())) #записываем все числа файла в список mx = -1 # максимальная сумма пары pair = [0,0] # элементы пары 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]) % 98 == 0: # проверка по условию mx = arr[i] + arr[j] # обновляем максимальную сумму pair = [arr[i],arr[j]] #обновляем элементы пары print(pair) # вывод ответа
#Эффективный алгоритм file = open(’27B__tcf5.txt’) #открытие файла n = int(file.readline()) #считываем первое число - количество чисел в файле div = 98 # наш делитель mx = [0]*div # список, в котором будет храниться максимальное число под каждым остатком при делении на 98 mx_sum = [0,0,0] # максимальная сумма пары for i in range(n): # проход по всему файлу x = int(file.readline()) # считываем текущее число need_ost = (div - x % div) % div # определяем необходимый остаток для второго числа чтобы в итоге получилась пара кратная 98 if x < mx[need_ost] and x + mx[need_ost] >= mx_sum[0]: # если первое число в паре больше второго и при этом сумма пары больше или равна максимальной mx_sum = [x + mx[need_ost],mx[need_ost],x]# то обновляем максимальную сумму, а также сохраняем числа пары mx[x % div] = max(mx[x % div],x) # обновляем максимальное число под определенным остатком, сравнивая текущее число с тем, что было записано в ячейке ранее. print(mx_sum[1],mx_sum[2]) # вывод чисел пары
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
