РЕШУ ЕГЭ — информатика

Задания

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

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

Файл A

Файл B

Первая строка входного файла содержит целое число N  — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма всех чисел не превышает 2 · 10⁹.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

Ответ:

Решение. Приведём решение на языке Python.

f = open("27-B.txt")

n = int(f.readline())

lefts = [0 for i in range(10)]

rights = [0 for i in range(10)]

for i in range(10):

lefts[i] = 0

rights[i] = 0

count = 0

sum = 0

for i in range(1, n + 1):

num = int(f.readline())

sum = sum + num

if num % 2 == 0:

count = count + 1

d = count % 10

if lefts[d] == 0:

lefts[d] = sum

rights[d] = sum

maxsum = 0

if count % 10 == 0:

print(sum)

else:

for i in range(1, count % 10 + 1):

if (rights[i] - lefts[i]) > maxsum:

maxsum = rights[i] - lefts[i]

if rights[0] > maxsum:

maxsum = rights[0]

print(maxsum)

Ответ: 4779554  979258630.

Примечание.

Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.

Приведём решение Матвея Курченко на языке Python.

f = [int(i) for i in open('27.txt')]

a = [-1] + [i-1 for i in range(1, f[0]+1) if f[i]%2 == 0] + [-1]

mx = 0

for i in range(1, (len(a)%10)):

mx = max(mx, sum(f[1:][a[i - 1] + 1:a[-(len(a)%10) + i]]))

print(mx)

Приведём решение на языке.

Будем последовательно считывать числа из файла. В массив lefts будем записывать первые встречающиеся суммы с количеством чётных элементов, делящимся на 10 с остатком от нуля до девяти. В массив rights также будем записывать суммы с количеством чётных элементов, делящимся на 10 с остатком от нуля до девяти. Если будет встречено несколько сумм с одним и тем же остатком, в массив rights будет записана сумма, встретившаяся позже. Если после считывания всех чисел из файла значение в переменной count не кратно 10, тогда будем проверять разности элементов массивов rights и lefts с соответствующими индексами и выводить на экран наибольшую из таких разностей  — это и будет искомой максимальной суммой.

Приведём решение задачи на языке Pascal.

var

i, n, num, count, d: integer;

sum, maxsum: int64;

lefts: array[0..9] of int64;

rights: array[0..9] of int64;

f: text;

begin

assign(f,'C:\27-B.txt');

reset(f);

readln(f, n);

for i := 0 to 9 do begin

lefts[i] := 0;

rights[i] := 0;

end;

count := 0;

sum := 0;

for i := 1 to n do begin

readln(f, num);

sum := sum + num;

if num mod 2 = 0 then count := count + 1;

d := count mod 10;

if lefts[d] = 0 then lefts[d] := sum;

rights[d] := sum;

end;

maxsum := 0;

if count mod 10 = 0 then writeln(sum)

else for i := 1 to (count mod 10) do

if (rights[i] - lefts[i]) > maxsum then maxsum := rights[i] - lefts[i];

if rights[0] > maxsum then maxsum := rights[0];

writeln(maxsum);

end.

В результате работы данного алгоритма при вводе данных из файла A ответ  — 4779554, из файла B  — 979258630.

№ п/п	№ задания	Ответ
1	38961	4779554 979258630

Ключ