Дана последовательность
Входные данные.
В первой строке входных данных задаётся количество
Пример организации исходных данных во входном файле:
6
40
40
120
30
50
110
Пример выходных данных для приведённого выше примера входных данных:
3 В ответе укажите два числа: сначала количество пар для
Ответ:
Пояснение. Из данных шести чисел можно составить три пары, удовлетворяющие условию: (40, 120), (40, 120), (50, 110). У пар (40, 40) и (30, 50) сумма делится
Сумма двух элементов
Создадим два массива по m элементов в каждом и будем хранить в них количество элементов последовательности, имеющих соответствующий остаток от деления
После завершения ввода количество подходящих пар с меньшим
Для остатков 0 и 40 остаток у чисел из пары совпадает, поэтому количество пар для этих остатков равно:
Общее количество пар можно найти как сумму пар по всем остаткам. Ниже приведена программа на алгоритмическом языке, реализующая этот алгоритм.
Приведём решение задачи на языке PascalABC.
const m = 80;
const b = 50;
var
a0: array[0..m-1] of integer;
a1: array[0..m-1] of integer;
i, N: integer;
x: integer;
p: integer;
s: integer;
f: text;
begin
for i := 0 to m-1 do begin
a0[i] := 0;
a1[i] := 0;
end;
assign(f,'28130_A.txt');
reset(f);
readln(f, N);
for i := 0 to N-1 do begin
readln(f, x);
p:= x mod m;
if x <= b then a0[p] := a0[p]+1
else a1[p] := a1[p]+1;
end;
p := 0;
s := a0[p]*a1[p] + ((a1[p]*(a1[p]-1)) div 2);
p := m div 2;
s := s + a0[p]*a1[p] + ((a1[p]*(a1[p]-1)) div 2);
for p := 1 to ((m div 2)-1) do
s := s + (a0[p]+a1[p])*a1[m-p] + a1[p]*a0[m-p];
writeln(s);
end.
В результате работы данного алгоритма при вводе данных из
Приведём решение задачи Давида Шамугия на языке PascalABC.
const m = 80;
const b = 50;
var
a:array[0..m-1,0..1] of integer;
i,j,n,x,c,t,p:integer;
f:text;
begin
c:=0;
for i:=0 to m-1 do
for j:=0 to 1 do
a[i,j]:=0;
assign(f,'C:\28130_A.txt');
reset(f);
readln(f,n);
readln(f,x);
for i:=1 to n-1 do begin
t:=0;
if x > b then t:=1;
inc(a[x mod m,t]);
readln(f,x);
p:=(m - x mod m) mod m;
if x > b then
c:=c+a[p,0]+a[p,1]
else
c:=c+a[p,1]
end;
print(c)
end.
В результате работы данного алгоритма при вводе данных из
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Петра Полякова на языке Python.
f=open('28130_B.txt')
n=int(f.readline())
numbers=[int(x) for x in f]
i=0
k=0
while i!=n:
for h in range(i+1,n):
if (numbers[i]+numbers[h])%80==0 and (numbers[i]>50 or numbers[h]>50):
k=k+1
i=i+1
print(k)
Приведём решение Бориса Савельева на языке Python.
f = open('28130_A.txt')
n = int(f.readline())
a = [0]*51
b = [0]*80
for i in range (0,n):
x = int(f.readline())
if x <= 50:
a[x%80] += 1
else:
b[x%80]+=1
ans = ((b[40]*(b[40]-1))//2) +((b[0]*(b[0]-1))//2)
for i in range (1,len(a)):
ans += a[i]*b[80-i]
if i <= 39:
ans += b[i] * b[80 - i]
print(ans)
Приведём решение Юрия Красильникова на языке Python.
a = [int(s) for s in open('28130_B.txt')][1:]
cnts = [[0]*2 for _ in range(80)]
k = 0
for x in a:
r = x%80
d = (80-r)%80
k += sum(cnts[d]) if x > 50 else cnts[d][0]
cnts[r][0 if x > 50 else 1] += 1
print(k)