Решение: Подсчёт пар, кратных 14
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на $14$.
В первой строке входных данных задаётся количество чисел $N$ ($1 \leq N \leq 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее $10\,000$. Программа должна вывести количество пар, в которых произведение элементов кратно $14$.
Пример входных данных:
4
2
6
7
21
Пример выходных данных:
4
Требуется написать эффективную по времени и по памяти программу. Алгоритм должен работать за время $O(N)$, а используемая память не должна зависеть от $N$ и не должна превышать 1 килобайт. Перед текстом программы необходимо кратко описать алгоритм решения и указать использованный язык программирования и его версию.
Решение по шагам
6 шаговДля произведения двух чисел быть кратным $14$, в произведении должны присутствовать множители $2$ и $7$. При обработке очередного числа считаем только пары с уже прочитанными числами, поэтому каждая пара учитывается ровно один раз.
$$14 = 2 \cdot 7$$Если текущее число чётное, оно уже содержит множитель $2$, поэтому ему подходят все предыдущие числа, кратные $7$. Если текущее число кратно $7$, ему подходят все предыдущие числа, кратные $2$.
Когда текущее число кратно $14$, предыдущие числа, кратные $14$, были посчитаны в обеих группах. Их нужно вычесть один раз.
$$\Delta = [x \bmod 2 = 0] \cdot c_7 + [x \bmod 7 = 0] \cdot c_2 - [x \bmod 14 = 0] \cdot c_{14}$$После подсчёта пар обновляем количества чисел, кратных $2$, $7$ и $14$. Все счётчики занимают постоянный объём памяти, а каждое число обрабатывается за постоянное время, поэтому сложность алгоритма равна $O(N)$ по времени и $O(1)$ по памяти.
$$T(N)=O(N),\quad M(N)=O(1)$$Пример реализации на Python 3.
Код:
n = int(input())
c2 = 0
c7 = 0
c14 = 0
answer = 0
for _ in range(n):
x = int(input())
if x % 2 == 0:
answer += c7
if x % 7 == 0:
answer += c2
if x % 14 == 0:
answer -= c14
if x % 2 == 0:
c2 += 1
if x % 7 == 0:
c7 += 1
if x % 14 == 0:
c14 += 1
print(answer)
Алгоритм с тремя счётчиками работает за $O(N)$ по времени и $O(1)$ по памяти. Подходит реализация на Python 3, приведённая в решении.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все пары, получая сложность $O(N^2)$.
Учитывать только пары, в которых одно число кратно $14$, хотя множители $2$ и $7$ могут находиться в разных числах.
Не вычитать числа, кратные $14$, когда текущее число также кратно $14$: такие пары считаются дважды.
Хранить всю последовательность, нарушая требование постоянного объёма памяти.