Дана последовательность натуральных чисел. Необходимо определить количество её непрерывных подпоследовательностей, сумма элементов которых
Входные данные.
Первая строка входного файла содержит целое
Вам даны два входных файла
Ответ:
Приведём решение на языке Python.
f = open("27-A (1).txt")
n = int(f.readline())
lefts = [0 for i in range(1000)]
count = 0
sumi = 0
for i in range(1, n + 1):
num = int(f.readline())
sumi += num
if sumi % 999 == 0:
count = count + 1
count += lefts[sumi % 999]
lefts[sumi % 999] += 1
print(count)
Ответ: 403 1801801220.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Юрия Красильникова на языке Python.
a = [int(s) for s in open('27.txt')][1:]
cnt = [1]+[0]*998
p = 0
for x in a:
p = (p+x)%999
cnt[p] += 1
print(sum([cnt[i]*(cnt[i]-1)//2 for i in range(999)]))
Приведём другое решение.
Если будет найдена подпоследовательность чисел с остатком от деления суммы элементов этой подпоследовательности
Приведём решение задачи на языке Pascal.
var
i, n, num, count: integer;
sum: int64;
lefts: array[0..998] of int64;
f: text;
begin
assign(f,'C:\27-B.txt');
reset(f);
readln(f, n);
for i := 0 to 998 do begin
lefts[i] := 0;
end;
count := 0;
sum := 0;
for i := 1 to n do begin
readln(f, num);
sum := sum + num;
if (sum mod 999 = 0) then count := count + 1;
count := count + lefts[sum mod 999];
lefts[sum mod 999] := lefts[sum mod 999] + 1;
end;
writeln(count);
end.
В результате работы данного алгоритма при вводе данных из
Приведём решение Сергея Донец на языке PascalABC.NET.
begin
var a := ReadAllLines('27.txt').Skip(1).Select(x -> x.ToInteger).ToArray;
var cnt := ArrGen(999, i -> Ord(i = 0));
var p := 0;
foreach var x in a do
begin
p := (p + x) mod 999;
cnt[p] += 1;
end;
var res := cnt.Select(c -> c * (c - 1) div 2).Sum;
Print(res);
end.