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

Задания

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

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

Файл A

Файл B

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.

Пример организации исходных данных во входном файле:

6 В ответе укажите два числа: сначала значение искомой длины для файла А, затем  — для файла B. Для приведенного примера ответ  — 7.

Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

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

f = open("27_B.txt")

n = int(f.readline())

mins = [1000000001 for i in range(43)]

minl = [0 for i in range(43)]

sum = 0

maxsum = 0

minlen = 0

ms = 0

l = 0

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

num = int(f.readline())

sum = sum + num

d = sum % 43

if d == 0:

maxsum = sum

minlen = i

else:

ms = sum - mins[d]

l = i - minl[d]

if ms > maxsum:

maxsum = ms

minlen = l

if (ms == maxsum) and (l < minlen):

maxsum = ms

minlen = l

if sum < mins[d]:

mins[d] = sum

minl[d] = i

print(minlen)

Ответ: 185  329329.

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

f = open('27_B.txt')

n = int(f.readline())

pr = [0]

a = [[1e9, -1] for i in range(43)]

a[0][0] = -1

for i in range(n):

x = int(f.readline())

pr.append(pr[i] + x)

a[pr[i+1]%43] = [min(i, a[pr[i+1]%43][0]), max(i, a[pr[i+1]%43][1])]

mx = ln = 0

for i in range(43):

if a[i][0] != 1e9 and a[i][1] != -1 and a[i][1] != a[i][0]:

s = pr[a[i][1]+1] - pr[a[i][0]+1]

if s > mx:

mx = s

ln = a[i][1] - a[i][0]

if s == mx and a[i][1] - a[i][0] < ln:

ln = a[i][1] - a[i][0]

print(ln)

Приведём решение Юрия Красильникова на языке Python.

a = [int(s) for s in open('27_B.txt')][1:]

p = 0

b = [0]

nk = [[0]] + [[] for _ in range(42)]

for i in range(len(a)):

p += a[i]

b.append(p)

r = p%43

if len(nk[r]) < 2: nk[r].append(i+1)

else: nk[r][1] = i+1

r = sorted([(b[x[1]]-b[x[0]],x[0]-x[1]) for x in nk if len(x) == 2],reverse=True)

print(-r[0][1])

Приведем другое решение.

Будем последовательно считывать числа из файла, суммируя все полученные числа. В массиве mins будем накапливать суммы с остатками от 0 до 42, в массиве minl будем накапливать длины для этих сумм. Каждую итерацию цикла будем проверять, делится ли текущая сумма на 43 без остатка. Если текущая сумма делится на 43 с определённым остатком, будем вычитать из неё сумму с таким же остатком из массива mins и записывать полученное значение в переменную maxsum (если полученная сумма будет больше текущего значения переменной), то же самое будем проделывать для минимальной длины последовательности.

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

var

i, d: longint;

n: longint;

mins: array [1..42] of longint;

minl: array [1..42] of longint;

sum, maxsum, minlen, num, ms, l: longint;

f: text;

begin

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

reset(f);

readln(f, n);

for i := 1 to 42 do mins[i] := 1000000001;

for i := 1 to 42 do minl[i] := 0;

sum := 0;

maxsum := 0;

minlen := 0;

ms := 0;

l := 0;

for i := 1 to n do begin

readln(f, num);

sum := sum + num;

d := sum mod 43;

if d = 0 then begin

maxsum := sum;

minlen := i;

end

else begin

ms := sum - mins[d];

l := i - minl[d];

if ms > maxsum then begin

maxsum := ms;

minlen := l;

end;

if (ms = maxsum) and (l < minlen) then begin

maxsum := ms;

minlen := l;

end;

if sum < mins[d] then begin

mins[d] := sum;

minl[d] := i;

end;

writeln(minlen);

end.

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

№ п/п	№ задания	Ответ
1	38604	185 329329

Ключ