Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Входные данные.
Даны два входных файла
Пример организации исходных данных во входном файле:
14
1
2
1
4
93
8
5
95
6
4
3
2
8
6 В ответе укажите два числа: сначала значение искомой длины для
Предупреждение: для обработки
Приведём решение на языке 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 будем накапливать суммы с остатками
Приведём решение задачи на языке 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;
end;
end;
writeln(minlen);
end.
В результате работы данного алгоритма при вводе данных из