Задача к ЕГЭ по информатике на тему «Цепочки, выбор последовательности, префиксные суммы» №2

Просмотров 7 Комментарии 0

Дано натуральное число $N$ , затем дана последовательность $N$ целых чисел. Необходимо найти максимально возможную сумму её непрерывной подпоследовательности, в которой количество положительных нечётных элементов кратно $50$ .

Входные данные:

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке одно целое число $N (1 ≤ N ≤ 10000000)$ — количество чисел. Каждая из следующих $N$ строк содержит целое число, меньшее 10000.

В ответе укажите два числа: сначала значение для файла $A$ , затем для файла $B$ .

Неэффективное решение

f = open("7A.txt")
n = int(f.readline())
ans = 0
a = []
for i in range(n):
    a.append(int(f.readline()))

for i in range(n):
    s = 0
    counter = 0  # счетчик полож. нечет. эл-ов
    for j in range(i, n):
        s += a[j]
        if (a[j] > 0) and (a[j] % 2 != 0):
            counter += 1
        if counter % 50 == 0:
            ans = max(ans, s)
print(ans)

Эффективное решение

f = open("7B.txt")
n = int(f.readline())
minpref = [0] + [100000000] * 49  # преф суммы по кол-ву полож.неч. чисел
ans, counter, s = 0, 0, 0
for i in range(n):
    x = int(f.readline())
    s += x
    if x > 0 and x % 2 != 0:
        counter += 1
    ans = max(ans, s - minpref[counter % 50])
    minpref[counter % 50] = min(s, minpref[counter % 50])
print(ans)

Ответ: 62164 25057