РЕШУ ЕГЭ — информатика

Задания

Дана последовательность N целых положительных чисел. Необходимо определить количество пар элементов этой последовательности, сумма которых делится на m  =  80 и при этом хотя бы один элемент из пары больше b  =  50.

Входные данные.

Файл A

Файл B

В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.

Пример организации исходных данных во входном файле:

120

110

Пример выходных данных для приведённого выше примера входных данных:

3 В ответе укажите два числа: сначала количество пар для файла А, затем для файла B.

Ответ:

Пояснение. Из данных шести чисел можно составить три пары, удовлетворяющие условию: (40, 120), (40, 120), (50, 110). У пар (40, 40) и (30, 50) сумма делится на 80, но оба элемента в этих парах не превышают 50.

Решение. Сумма двух элементов кратна m, если сумма их остатков от деления на m равна m или 0.

Создадим два массива по m элементов в каждом и будем хранить в них количество элементов последовательности, имеющих соответствующий остаток от деления на m; в массиве a0 будем подсчитывать элементы, не превышающие b, в массиве a1  — превышающие.

После завершения ввода количество подходящих пар с меньшим остатком p от 1 до 39 можно подсчитать по формуле:

(a0[p] + a1[p])*a1[m−p] + a1[p]*a0[m−p].

Для остатков 0 и 40 остаток у чисел из пары совпадает, поэтому количество пар для этих остатков равно:

a0[p]*a1[p] + a1[p]*(a1[p]−1)/2.

Общее количество пар можно найти как сумму пар по всем остаткам. Ниже приведена программа на алгоритмическом языке, реализующая этот алгоритм.

Приведём решение задачи на языке 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.

В результате работы данного алгоритма при вводе данных из файла A ответ  — 3, из файла B  — 625350.

Приведём решение задачи Давида Шамугия на языке 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.

В результате работы данного алгоритма при вводе данных из файла A ответ  — 3, из файла B  — 625350.

Примечание.

Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.

Приведём решение Петра Полякова на языке 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)

№ п/п	№ задания	Ответ
1	28130	3 625350

Ключ