Задание №27 ЕГЭ Информатика с ответом и решением

Сумма двух элементов кратна 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)

Приведём решение Сергея Донец на PascalABC.NET:

uses School;

begin

var m:=80;

var b:=50;

var pa:=ReadAllLines('28130_A.txt').Skip(1).Select(x->x.ToInteger);

var pb:=ReadAllLines('28130_B.txt').Skip(1).Select(x->x.ToInteger);

pa.Combinations(2).Count(arr-> begin var (x, y) := (arr[0], arr[1]);

Result := ((x + y) mod m = 0) and ((x > b) or (y > b));end).Print;

pb.Combinations(2).Count(arr-> begin var (x, y) := (arr[0], arr[1]);

Result := ((x + y) mod m = 0) and ((x > b) or (y > b));end).Print;

end.