Задача с сайта для подготовки к ЕГЭ по информатике

Question

На вход программы поступает последовательность из N натуральных чисел. Рассматриваются все пары различных элементов последовательности, между которыми есть хотя бы один (внутренний) элемент. Необходимо определить наибольшую сумму элементов пары, для которой сумма всех внутренних элементов кратна K.

Входные данные. Даны два входных файла (Файл А и Файл В), каждый из которых в первой строке содержит натуральное число K (1 ≤ K ≤ 10^9) и натуральное число N – количество чисел (1 ≤ N ≤ 10^9). В каждой из следующих N строк записаны элементы последовательности – натуральные числа, не превышающие 10^9.

Пример входного файла:

10 6

9

1

4

7

3

8

При таких исходных данных наибольшей суммой будет 12 для пары (4, 8). В этом случае сумма всех внутренних элементов 7 + 3 = 10 делится на K = 10. Ответ: 12. В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

Не могу решить файл В. Уже бьюсь в конвульсиях! Пожалуйста, помогите написать код для решения файла B!

ОТВЕТЫ: 1973 на файл А, 186888 на файл В

with open('<пути до файла A>', 'r') as file:
pars = []
k, n = file.readline().split()
r = [int(i) for i in file.readlines() if i != '\n']

for j in range(1, int(n)-1):
    summ = sum(r[j:-1])
    for i in range(int(n)-2, j-1, -1):
        if summ < int(k):
            break
        elif summ % int(k) == 0:
            pars.append(r[j-1] + r[i+1])
            summ -= r[i]
        else:
            summ -= r[i]


print(max(pars))

Answer 1

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

Возьмем для примера k=10 и список, ниже его префиксные суммы по модулю 10

              *        *
a = [2, 9, 1, 4, 7, 3, 8, 20, 7, 13]
     2  1  2  6  3  6  4  4   1  4
              ^     ^

Можно заметить, что одинаковые префиксные суммы соответствуют последовательностям, сумма которых по модулю k равна нулю.

При этом индексы обрамляющих чисел соответствуют индексу первой суммы и индексу, следующему после второй суммы. Например, для двух одинаковых сумм 6 внешние числа из первого списка - 4 и 8.

Заметим, что для каждого значения префиксной суммы достаточно запоминать максимальное число из списка, соответствующее ей:

def best_inner(a, n, k):
    maxx = 0
    psum = a[0] % k
    maxmodk = dict()
    for i in range(1, n):
        if psum in maxmodk:
            maxx = max(maxmodk[psum] + a[i], maxx)
            maxmodk[psum] = max(maxmodk[psum], a[i-1])
        else:
            maxmodk[psum] = a[i-1]
        psum = (psum + a[i]) % k
    return maxx

with open('D:/Prog/PyProj/27-153b.txt', 'r') as file:
    k, n = file.readline().split()
    a = [int(i) for i in file.readlines() if i != '\n']

print(best_inner(a, len(a), int(k)))


>>> 186888

Answer 2

Мой ответ использует тот же алгоритм что и ответ MBo, но не загружает файл целиком в память. Сложность по памяти O(k) - от объёма файла не зависит. Сложность по времени O(n + k):

# k - модуль, n - число элементов последовательности
k, n = map(int, input().split())

# текущая максимальная сумма пары
max_so_far = 0

# текущий максимальный левый элемент пары для данного остатка по модулю k
# ноль означает что такого элемента ещё не было
max_left_so_far = [0] * k

# предыдущий элемент последовательности
prev_v = 0

# накопительная сумма по модулю k
r = 0

# читаем последовательность
# обработка первого элемента не меняет максимумы, но обновляет r и prev_v
# обработка остальных элементов также обновляет максимумы
for _ in range(n):
    v = int(input())

    # если для данного остатка есть левые границы
    if max_left_so_far[r] > 0:
        # обновляем максимальную сумму пары
        max_so_far = max(max_so_far, max_left_so_far[r] + v)

    # обновляем максимальный левый элемент пары
    max_left_so_far[r] = max(max_left_so_far[r], prev_v)

    # обновляем накопительную сумму по модулю k
    r = (r + v) % k

    # запоминаем предыдущий элемент
    prev_v = v

print(max_so_far)

$ time python best-pair.py < 27-153a.txt
1973

real  0m0.034s
user  0m0.032s
sys   0m0.000s

$ time python best-pair.py < 27-153b.txt
186888

real  0m0.336s
user  0m0.300s
sys   0m0.032s

БЛОГ НА HUSL

Задача с сайта для подготовки к ЕГЭ по информатике

Ответы (2 шт):