Сайт Богданова Дмитрия Валериевича

Задание №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.

Решение

Сумма двух чисел кратна 12, если сумма остатков от деления на 12 этих чисел также кратна 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.
Подробнее...
Добавить комментарий
Комментарии (0)