Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее
10 000.
Пример организации исходных данных во входном файле:
7
1
3
4
93
8
5
95
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем – для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
В ответе запишите два числа: ПЕРВОЕ – число, полученное из первого файла; ВТОРОЕ – число, полученное из второго файла.
Ответ:
(полученное из первого файла)
(полученное из второго файла)
Демонстрационный вариант ЕГЭ 2022 г. – задание №27
Решение:
27-A
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
f = open('27_A.txt') n = int(f.readline()) a = [] for i in range(n): a.append(int(f.readline())) m, mk = 0, 0 for i in range(n-1): s = a[i] k = 1 for j in range(i+1, n): s += a[j] k += 1 if s % 43==0: if s>m or (s==m and k<mk): m=s mk=k print(mk) |
Ответ: 185
27-B
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
f = open('27_B.txt') n = int(f.readline()) s = 0 res = [] maxs = [0] + [False]*42 lens = [0] + [False]*42 for i in range(1, n+1): s += int(f.readline()) ost = s%43 if maxs[ost] != False: res.append([s-maxs[ost], lens[ost]-i]) else: maxs[ost] = s lens[ost] = i print(max(res)) |
Ответ: 329329