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

Произведение двух чисел делится на 26, если выполнено одно из следующих условий (условия не могут выполняться одновременно).

А. Оба сомножителя делятся на 26.

Б. Один из сомножителей делится на 26, а другой не делится.

В. Ни один из сомножителей не делится на 26, но один сомножитель делится на 2, а другой — на 13.

Примечание для проверяющего. Условие делимости произведения на 26 можно сформулировать проще, например так: (один из сомножителей делится на 26) ИЛИ (один сомножитель делится на 2, а другой — на 13). Но в этом случае пара сомножителей может удовлетворять обоим условиям, что затруднит подсчёт количества пар.

При вводе чисел можно определять, делится ли каждое из них на 26, 2 и 13, и подсчитывать следующие значения:

1) n26 — количество чисел, кратных 26;

2) n13 — количество чисел, кратных 13, но не кратных 26;

3) n2 — количество чисел, кратных 2, но не кратных 26.

Примечание для проверяющего. Сами числа при этом можно не хранить. Каждое число учитывается не более чем в одном из счётчиков. Количество пар, удовлетворяющих условию А, можно вычислить по формуле n26 · (n26 – 1) : 2.

Количество пар, удовлетворяющих условию Б, можно вычислить по формуле n26 · (N – n26).

Количество пар, удовлетворяющих условию В, можно вычислить по формуле n2 · n13.

Поэтому искомое количество пар вычисляется по формуле n26 · (n26 – 1) : 2 + n26 · (N – n26) + n2 · n13.

Приведём решение задачи на языке PascalABC.

var

N: integer; {количество чисел}

a: integer; {очередное число}

n26, n13, n2: integer;

k26: integer; {количество требуемых пар}

i: integer;

f: text;

begin

n26:=0; n13:=0; n2:=0;

assign(f,'27989_A.txt');

reset(f);

readln(f, n);

for i := 1 to n do begin

readln(f, a);

if a mod 26 = 0 then

n26 := n26+1

else if a mod 13 = 0 then

n13 := n13 + 1

else if a mod 2 = 0 then

n2 := n2 + 1;

end;

k26 := n26*(n26-1) div 2 + n26*(N-n26) + n2*n13;

writeln(k26)

end.

Приведём решение Михаила Бурмистрова на языке PascalABC.

var f:text;

a: array [1..100000] of integer;

n,i,j,p,count:integer;

begin

assign(f,'C:\27989_A.txt');

reset(f);

readln(f,n);

for i:=1 to n do readln(f,a[i]);

for i:=1 to n-1 do

for j:=i+1 to n do begin

p:=a[i]*a[j];

if p mod 26 =0 then inc(count);

end;

writeln(count);

end.

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

Примечание.

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

Приведём другое решение на языке Python.

f = open("27989_B.txt") # для файла A укажите его название

s = f.readlines()

n = int(s[0])

k = 0

k_0 = 0

k_26 = 0

k_2 = 0

k_13 = 0

for i in range(1, n + 1):

s[i] = int(s[i])

if s[i] % 26 == 0:

k_26 += 1

elif s[i] % 13 == 0:

k_13 += 1

elif s[i] % 2 == 0:

k_2 += 1

else:

k_0 += 1

k = k_26 * k_0 + k_13 * k_2 + k_26 * k_13 + k_26 * k_2 + (k_26 * (k_26 - 1)) // 2

print(k)

Приведём решение Юрия Красильникова на языке Python.

#Решение на питоне, подсчет чисел с разной делимостью:

a=[int(s) for s in open('27989_B.txt')][1:]

m2=len([x for x in a if x%2==0 and x%13!=0])

m13=len([x for x in a if x%13==0 and x%2!=0])

m26=len([x for x in a if x%26==0])

m=len(a)

print(m26*(m26-1)//2 + m26*(m-m26) + m2*m13)

Приведём решение Юрия Красильникова на языке Python.

#Выбираем числа последовательности по очереди и прибавляем к счетчику пар число пар, которое очередное число образует с предыдущими:

a = [int(s) for s in open('27989_B.txt')][1:]

cnts = [0]*4

k = 0 # счетчик количества пар

for x in a:

n = (x%2==0)*2 + (x%13==0) # n=0 - не делится ни на 2, ни на 13.

# n=2 - делится на 2; n=1 - делится на 13; n=3 - делится на 26;

if n == 3:

k += sum(cnts)

elif n != 0:

k += cnts[3-n] + cnts[3]

else: k += cnts[3]

cnts[n] += 1

print(k)