Первая строка входного файла содержит целое число 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)]))
Приведём другое решение Юрия Красильникова на языке Python.
#Идея - для очередного элемента определяем число последовательностей, которое он образует с уже рассмотренными,
#и прибавляем это число к результату.
a = [int(s) for s in open('27.txt')][1:]
cnt = [1]+[0]*998
p,m = 0,0
for x in a:
p = (p+x)%999
m += cnt[p]
cnt[p] += 1
print(m)
Приведём другое решение.
Если будет найдена подпоследовательность чисел с остатком от деления суммы элементов этой подпоследовательности на 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;
Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма всех чисел и число в ответе не превышают 2 · 109 по абсолютной величине.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Ответ:
Решение.
Приведём решение на языке Python.
f = open("27-B.txt")
n = int(f.readline())
lefts = [0 for i in range(1111)]
count = 0
sumi = 0
for i in range(1, n + 1):
num = int(f.readline())
sumi += num
if sumi % 1111 == 0:
count = count + 1
count += lefts[sumi % 1111]
lefts[sumi % 1111] += 1
print(count)
Ответ: 344 1620157920.
Приведём решение Юрия Красильникова на языке Python.
nums = [int(s) for s in open('27-B.txt') ][1:]
rems = [1]+[0]*1110
s=0
for x in nums:
s+=x
rems[s%1111] += 1
print(sum([x*(x-1)//2 for x in rems]))
Приведём другое решение.
Если будет найдена подпоследовательность чисел с остатком от деления суммы элементов этой подпоследовательности на 1111равным 1, чтобы сумма элементов найденной подпоследовательности была кратна 1111, достаточно вычесть из неё сумму элементов другой подпоследовательности с остатком 1. Объявим массив lefts, в котором будем хранить количество найденных подпоследовательностей с остатком от деления суммы элементов этой подпоследовательности на 1111от 0 до 1110. Каждый раз, находя подпоследовательность с тем или иным остатком от деления суммы элементов этой подпоследовательности на 1111, будем прибавлять к переменной count хранящееся в массиве lefts значение с соответствующим остатком от деления суммы элементов этой подпоследовательности.
Приведём решение задачи на языке Pascal.
var
i, n, num, count: integer;
sum: int64;
lefts: array[0..1110] of int64;
f: text;
begin
assign(f,'C:\27-B.txt');
reset(f);
readln(f, n);
for i := 0 to 1110 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 1111 = 0) then count := count + 1;
count := count + lefts[sum mod 1111];
lefts[sum mod 1111] := lefts[sum mod 1111] + 1;
end;
writeln(count);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 344, из файла B — 1620157920.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
