Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 67. Найдите среди них подпоследовательность с максимальной суммой. Укажите в ответе найденную максимальную сумму.
Входные данные
Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке количество чисел N (1 < N < 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
7
1
3
4
93
8
5
95
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем — для файла В.
Апробация ЕГЭ по информатике 19 февраля 2022 – задание №27
Тренировочный экзамен по информатике и ИКТ (КЕГЭ) в компьютерной форме
Решение:
Решение только на 27-A
|
1 2 3 4 5 6 7 8 9 10 11 |
f = open('27_A.txt') n = int(f.readline()) a = [int(s) for s in f] m = 0 for i in range(n): s = 0 for j in range(i, n): s += a[j] if s % 67==0 and s>m: m=s print(m) |
Решение только на 27-B
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
f = open('27_B.txt') n = int(f.readline()) s = 0 res = [] maxs = [-1]*67 maxs[0]=0 for i in range(n): s += int(f.readline()) ost = s%67 if maxs[ost] != -1: res.append(s-maxs[ost]) else: maxs[ost] = s print(max(res)) |
Решение — Каримов Минтимер Ростямович
|
1 2 3 4 5 6 7 8 9 |
input=open('27_B.txt').readline k=67 p=[float('inf')]*k p[0]=ans=sm=0 for _ in range(int(input())): sm+=int(input()) ans=max(ans,sm-p[sm%k]) p[sm%k]=min(p[sm%k],sm) print(ans) |
Ответ: 649565
208957389