Задание EGEINFF291D4: Эффективная обработка данных и кластеры

Решение.

Обрабатываем два приложенных текстовых файла отдельно. В файле A содержится 776 записей, в файле B — 1751438. Заголовок задаёт параметры и не является элементом последовательности. Порядок исходных записей сохраняем. Числа из иллюстративного примера не заменяют данные файлов.

Пусть P₀ = 0, Pᵣ — сумма первых r чисел. Сумма от l + 1 до r равна Pᵣ − Pₗ. Она делится на 43 тогда и только тогда, когда остатки Pᵣ и Pₗ при делении на 43 совпадают.

Все исходные числа положительны, поэтому префиксные суммы строго возрастают. Для фиксированного правого конца наибольшая сумма получается при самом раннем префиксе с нужным остатком. Храним только первую пару «сумма, позиция» для каждого остатка. Остаток ноль сначала соответствует пустому префиксу (0, 0); это позволяет учитывать отрезки с первого элемента.

При каждом новом правом конце сначала сравниваем сумму с текущим максимумом. Только при равных максимальных суммах выбираем меньшую длину r − l. Искомый ответ — длина выбранного отрезка, а не его сумма. Проверка выполняется до добавления нового остатка, поэтому пустой отрезок не рассматривается. Последующие префиксы того же остатка не заменяют первый: для любого будущего конца они дают строго меньшую сумму.

Распакуем архив и положим указанные в программе текстовые файлы рядом с ней. Программа печатает результат для A, затем для B:

from array import array

def solve(name):
    mod = 43
    first = {0: (0, 0)}
    prefix = 0
    best_sum = None
    best_length = None
    with open(name, encoding="utf-8-sig") as f:
        n = int(f.readline())
        for r in range(1, n + 1):
            prefix += int(f.readline())
            rem = prefix % mod
            if rem in first:
                base, l = first[rem]
                value = prefix - base
                length = r - l
                if (best_sum is None or value > best_sum
                        or value == best_sum and length < best_length):
                    best_sum = value
                    best_length = length
            else:
                first[rem] = (prefix, r)
    return best_length

print(solve('301_27_A.txt'), solve('301_27_B.txt'))

Время O(N), дополнительная память O(k), где k — делитель. Считывание и все арифметические действия выполняются над целыми числами; округление вычисленных ответов не требуется.

Проверка на исходных файлах. Номера элементов ниже отсчитываются от 1; полный алгоритм проверяет все допустимые варианты, а указанные позиции показывают достижение найденного результата.

Для каждой строки длина равна конец − начало + 1. Указанные суммы делятся на 43; при сравнении всех максимальных сумм применено правило минимальной длины.

Ответ: 185 329329.