Задача № 184
Компания, ведущая мониторинг линии электропередач, получила N числовых значений измерений высоты растений (в мм) вдоль этой линии, которые выполнялись последовательно друг за другом.
Высоту растений с точки зрения безопасности линии электропередач оценивают на основе анализа сумм всех возможных непрерывных подпоследовательностей полученных числовых значений, среди которых требуется выбрать подпоследовательность с максимальной суммой, кратной k = 137. Среди таких непрерывных подпоследовательностей необходимо выбрать подпоследовательность с наибольшим количеством элементов, то есть ту, в которой суммируются числовые значения высот наибольшего количества растений. В ответе укажите её длину.
Входные данные
Дано два входных файла (файл А и файл В), каждый из которых в первой строке содержит число N \((1 \leqslant N \leqslant 10 000 000)\) - количество измерений высоты растений (в мм). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000 - числовое значение одного результата измерения.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем - для файла В.
Типовой пример организации данных во входном файле
7
100
300
400
9300
800
500
9500
При таких исходных данных при k = 5000 искомая максимальная сумма составляет 300 + 400 + 9300 или 500 + 9500 и равна 10000; ответом на вопрос задачи является число 3.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Решение
Код из видео
# открываем файл B
file = open('27-B.txt')
# считываем первую строку
N = int(file.readline())
# по условию
k = 137
# максимальный ответ
# сначала сумма, затем количество
maxA = (0, 0)
# общая сумма и количество
s = count = 0
# словарь с остатками: алгоритм префиксной суммы
# для кратных числе ничего уменьшать не будет: по умолчанию нули
ost = { 0:(0, 0) }
# перебираем строки
for line in file:
# преобразуем каждую строку в число
num = int(line)
# увеличиваем общую сумму и количество
s += num
count += 1
# находим подходящий остаток или сохраняем текущий
ost[s % k] = ost.get(s % k, (s, count))
# делим остаток на сумму и количество
ostS, ostC = ost[s % k]
# находим максимум: сначала сравниваем суммы,
# а при их равестве по количеству
maxA = max(maxA, (s - ostS, count - ostC))
# в ответе только количество
print(maxA[-1])