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

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

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

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

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

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

f = open(’27B_2__1natt.txt’)
n = int(f.readline())
mx = 0 # максимальная сумма подпоследовательности
s = 0 # сумма всех чисел файла
count = 0 # количество нечётных чисел всего файла
K = 10 # чему должно быть кратно количество нечётных чисел
tails = [10**30]*K # список, в котором под каждым индексом будут записаны минимальные префиксные суммы.
# определенный индекс обозначает остаток при делении на 3.
# Например, tails[2] - это префиксная сумма, у которой количество нечётных чисел даёт остаток 2 при делении на 10
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if x % 2 != 0: # если текущее число - нечётное
        count += 1 # увеличиваем счётчик
    if count % K == 0: # если счётчик кратен 10
        mx = max(mx,s) # перезаписываем максимум
    # если в сумме s количество нечётных чисел не кратно 10
    # тогда убавляем такую префиксную сумму,
    # после которой в полученной подпоследовательности количество нечётных чисел будет кратно 10
    s1 = s - tails[count % K]
    mx = max(mx,s1) # перезаписываем максимум
    # перезаписываем префиксные суммы под определенным остатком при делении на 10
    tails[count % K] = min(tails[count % K], s)
print(mx)

Ответ: 103546 5493881388