Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких под последовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них. Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 10 8 ). Каждая из следующих N строк содержит натуральное число, не превышающее 10000.
Arnfinn пометил как избранный вопрос 01.11.2023
1 Ответ
var
i, d: longint;
n: longint;
mins: array [0..42] of longint;
minl: array [0..42] of longint;
sum, maxsum, minlen, num, ms, l: longint;
f: text;
begin
assign(f,'C:\27_B.txt');
reset(f);
readln(f, n);
for i := 0 to 42 do mins[i] := 1000000001;
for i := 0 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;
end;
if sum < mins[d] then begin
mins[d] := sum;
minl[d] := i;
end;
end;
writeln(minlen);
end.
ответ — 185, из файла B — 329329.
Arnfinn изменил статус на опубликованный 14.01.2022