Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма всех чисел и число в ответе не превышают 2 · 109 по абсолютной величине.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Ответ:
Решение. Приведём решение на языке 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)]))
Приведём другое решение.
Если будет найдена подпоследовательность чисел с остатком от деления суммы элементов этой подпоследовательности на 999равным 1, чтобы сумма элементов найденной подпоследовательности была кратна 999, достаточно вычесть из неё сумму элементов другой подпоследовательности с остатком 1. Объявим массив lefts, в котором будем хранить количество найденных подпоследовательностей с остатком от деления суммы элементов этой подпоследовательности на 999от 0 до 998. Каждый раз, находя подпоследовательность с тем или иным остатком от деления суммы элементов этой подпоследовательности на 999, будем прибавлять к переменной count хранящееся в массиве lefts значение с соответствующим остатком от деления суммы элементов этой подпоследовательности.
Приведём решение задачи на языке 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.
В результате работы данного алгоритма при вводе данных из файла A ответ — 403, из файла B — 1801801220.
Приведём решение Сергея Донец на языке 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;
PDF-версии: 