Задание №1702/27

Задание

Дан набор из \(N\) натуральных чисел. Необходимо определить количество пар элементов \(\left(a_{i},a_{j}\right)\) этого набора, в которых \(1\leq i<j\leq N\) и сумма элементов кратна 12.

Напишите эффективную по времени и по памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел \(N\) в \(k\) раз время работы программы увеличивается не более чем в \(k\) раз. Программа считается эффективной по памяти, если память, необходимая для хранения переменных программы, не превышает одного килобайта и не увеличивается с ростом \(N\).

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел \(N\) (\(1\leq N\leq10000\)). В каждой из последующих \(N\) строк записано одно натуральное число, не превышающее 1000.

Пример входных данных:

	5
	7
	5
	6
	12
	24

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

	2

В приведённом наборе из 5 чисел имеются две пары \(\left(5,7\right)\), \(\left(12,24\right)\), сумма элементов которых кратна 12.

Решение

Замечание

var
  a : array[0..3, 0..2] of integer;
  N, x, d3, d4, i, j : integer;
  s : longint;
begin
  for i := 0 to 3 do
    for j := 0 to 2 do
      a[i, j] := 0; 
  s := 0;
  readln(N);
  for i := 1 to N do begin
    readln(x);
    d3 := x mod 3;
    d4 := x mod 4;
    s := s + a[(4 - d4) mod 4, (3 - d3) mod 3];
    a[d4, d3] := a[d4, d3] + 1
  end;
  writeln(s)
end.

Ответ

var
  rem : array[0..11] of integer;
  N, i, x : integer;
  m : longint;
begin
  for i := 0 to 11 do
    rem[i] := 0; 
  readln(N);
  for i := 1 to N do begin
    readln(x);
    inc(rem[x mod 12])
  end;
  m := (rem[0] * (rem[0] - 1) + rem[6] * (rem[6] - 1)) div 2;
  for i := 1 to 5 do
    m := m + rem[i] * rem[12 - i];
  writeln(m)
end.