Дана последовательность целых чисел. Необходимо найти максимально возможную сумму её непрерывной подпоследовательности, в которой количество положительных чётных элементов кратно k = 30.
Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма любой выборки заданных чисел не превышает 2 · 109 по абсолютной величине.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Ответ:
Решение. Приведём решение на языке Python.
f = open("27-B.txt")
n = int(f.readline())
lefts = [0 for i in range(30)]
maxsum = 0
for i in range(30):
lefts[i] = 2 * 1000000000
count = 0
sum = 0
for i in range(1, n + 1):
num = int(f.readline())
sum = sum + num
if (num % 2 == 0) and (num > 0):
count = count + 1
d = count % 30
if sum < lefts[d]:
lefts[d] = sum
maxsum = max(maxsum, sum - lefts[d])
print(maxsum)
Ответ: 97011 24932.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение.
Для нахождения искомой суммы найдём сумму всех чисел в файле и, если количество чётных положительных чисел этой суммы не будет кратно 30, вычтем из этой суммы число, являющееся минимальной подсуммой чисел с таким же количеством чётных положительных чисел, кратных 30, как и у суммы всех чисел в файле.
Будем последовательно считывать числа из файла. В массив lefts будем записывать первые встречающиеся суммы с количеством чётных элементов, делящимся на 30 с остатком от нуля до двадцати девяти. Каждое считанное число будем прибавлять к переменной sum. Если очередное встреченное число является чётным и положительным, будем увеличивать значение счётчика count. Каждую итерацию цикла будем проверять, больше ли текущая максимальная сумма в переменной maxsum больше значения выражения sum − lefts[d] (в этом выражении получаем значение новой подсуммы, с количеством чётных положительных чисел кратным 30). Если значение переменной maxsum меньше — обновляем её значение.
Приведём решение задачи на языке Pascal.
var
i, n, num, count, d: integer;
sum, maxsum: int64;
lefts: array[0..29] of int64;
f: text;
begin
assign(f,'C:\27-B.txt');
reset(f);
readln(f, n);
for i := 0 to 29 do begin
lefts[i] := 2 * 1000000000;
end;
count := 0;
sum := 0;
for i := 1 to n do begin
readln(f, num);
sum := sum + num;
if (num mod 2 = 0) and (num > 0) then count := count + 1;
d := count mod 30;
if sum < lefts[d] then lefts[d] := sum;
maxsum := Max(maxsum, sum - lefts[d]);
end;
writeln(maxsum);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 97011, из файла B — 24932.
PDF-версии: 