Дана последовательность N целых положительных чисел. Необходимо определить количество пар элементов этой последовательности, сумма которых делится на m = 80 и при этом хотя бы один элемент из пары больше b = 50.
Описание входных и выходных данных.
В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
6
40
40
120
30
50
110
Пример выходных данных для приведённого выше примера входных данных:
3
Пояснение. Из данных шести чисел можно составить три пары, удовлетворяющие условию: (40, 120), (40, 120), (50, 110). У пар (40, 40) и (30, 50) сумма делится на 80, но оба элемента в этих парах не превышают 50.
Требуется написать эффективную по времени и по памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, — 4 балла. Максимальная оценка за правильную программу, эффективную только по времени — 3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла. Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите используемый язык программирования и его версию.
Сумма двух элементов кратна m, если сумма их остатков от деления на m равна m.
Создадим два массива по 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.
Общее количество пар можно найти как сумму пар по всем остаткам. Ниже приведена программа на языке Pascal, реализующая этот алгоритм.
Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти.
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; | количество пар
begin
for i := 0 to m-1 do begin
a0[i] := 0;
a1[i] := 0;
end;
readln(N);
for i := 0 to m-1 do begin
readln(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.
Возможно также «лобовое» решение: запишем все исходные числа в массив, переберём все возможные пары и подсчитаем подходящие. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растёт квадратично). Подобная программа оценивается не выше 2 баллов.
Пример 2. Правильная, но неэффективная программа на языке Pascal.
const m = 80;
b = 50;
var
N: integer; {количество чисел}
a: array [1..10000] of integer; {исходные данные}
s: integer; {ответ – количество пар}
i,j: integer;
begin
readln(N);
for i:=1 to N do readln(a[i]);
s:=0;
for i := 1 to N-1 do begin
for j := i+1 to N do begin
if ((a[i] + a[j]) mod m = 0) and ((a[i] > b) or (a[j]) > b))
then s := s + 1
end
end;
writeln(s)
end.