Решение: Подсчёт пар с произведением
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять рядом, порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на $6$.
В первой строке входных данных задаётся количество чисел $N$ ($1 \leq N \leq 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее $10\,000$.
Программа должна вывести одно число — количество пар, в которых произведение элементов кратно $6$.
Пример входных данных:
$4$
$2$
$10$
$3$
$15$
Пример выходных данных: $4$.
Из четырёх заданных чисел можно составить $6$ попарных произведений. На $6$ делятся произведения $2 \cdot 3$, $2 \cdot 15$, $10 \cdot 3$ и $10 \cdot 15$.
Требуется написать эффективную по времени и по памяти программу. Программа считается эффективной по времени, если при увеличении $N$ в $k$ раз время её работы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память для хранения всех переменных не превышает $1$ килобайта и не увеличивается с ростом $N$.
Перед текстом программы необходимо кратко описать алгоритм решения и указать использованный язык программирования и его версию.
Решение по шагам
5 шаговДля каждого числа достаточно знать два булевых признака: делится ли оно на $2$ и делится ли оно на $3$. Это определяет один из четырёх типов числа.
Произведение двух чисел делится на $6$, если среди двух чисел есть хотя бы один множитель $2$ и хотя бы один множитель $3$. Поэтому для очередного числа можно добавить к ответу количество уже обработанных чисел совместимых с его типом.
После подсчёта подходящих предыдущих чисел увеличить счётчик типа текущего числа. Так каждая пара учитывается ровно один раз — в момент обработки второго элемента пары.
$$O(N)\text{ по времени и }O(1)\text{ по дополнительной памяти}$$Эталонная реализация на Python 3.11:
from sys import stdin
n = int(stdin.readline())
cnt = [[0, 0], [0, 0]]
answer = 0
for _ in range(n):
x = int(stdin.readline())
d2 = int(x % 2 == 0)
d3 = int(x % 3 == 0)
for p2 in range(2):
for p3 in range(2):
if (d2 or p2) and (d3 or p3):
answer += cnt[p2][p3]
cnt[d2][d3] += 1
print(answer)
Алгоритм работает за $O(N)$ времени и использует $O(1)$ дополнительной памяти.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все пары, получая сложность $O(N^2)$.
Проверять только делимость на $2$ или только делимость на $3$, забывая о необходимости одновременной делимости на оба множителя.
Увеличивать счётчик типа до подсчёта пар, из-за чего число может образовать пару само с собой.
Хранить всю последовательность, хотя для решения достаточно четырёх счётчиков.
Использовать обычный целочисленный тип с недостаточным диапазоном для ответа: максимально возможное число пар равно $\frac{N(N-1)}{2}$.