Python. Задача 8-40

На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности a_i и a_j, такие что i < j и a_i > a_j (первый элемент пары больше второго; i и j — порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 120. Если среди найденных пар максимальную сумму имеют несколько, то необходимо вывести последнюю их них.

Входные данные: Дан входной файл, в первой строке которого задаётся количество чисел n (2 ≤ n ≤ 100 000). В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, то необходимо вывести из них последнюю, встреченную в файле . Гарантируется, что хотя бы одна такая пара в последовательности есть.

Пример входных данных:
6
60
140
61
100
300
59

Пример выходных данных для приведённого выше примера входных данных: 140 100

Пояснение. Из шести заданных чисел можно составить три пары, сумма элементов которых делится на m=120: 60+300, 140+100 и 61+59. Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.

Ответ

9979 9941

Решение

# Делитель из условия задачи
m = 120
f = open('c:\\work\\test-8-40-1.txt')
# Считываем из первой строки количество чисел
N = int(f.readline())
# Пара с максимальной суммой, которая делится на m
left = 0
right = 0
# Cписок максимальных значений, соответствующих остатку от деления его на m
a = [0] * m
# Для каждого числа из файла вычисляем сумму и сравниваем с максимальной
for i in range(N):
    x = int(f.readline())
    # Вычисляем индекс списка для текущего числа
    p = x % m
    # Вычисляем индекс списка для парного числа
    idx = (m - p) % m
    # Текущую сумму пары сравниваем с максимальной
    # при условии, что парное число больше текущего
    if a[idx] > x and a[idx] + x >= left + right:
        left = a[idx]
        right = x
    # Обновляем максимальное значение в списке
    if a[p] < x:
        a[p] = x
f.close()
print(left, right)

◄▲►