Решение: Подсчёт пар с произведением
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: элементы пары могут быть расположены в последовательности не рядом, порядок элементов в паре неважен. Необходимо определить количество пар, для которых произведение элементов делится без остатка на $10$.
В первой строке входных данных задаётся количество чисел $N$ ($1 \leq N \leq 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее $10\,000$.
В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно $10$.
Пример входных данных:
4
2
6
5
15
Пример выходных данных:
4
Из четырёх заданных чисел можно составить 6 попарных произведений: $2\cdot6$, $2\cdot5$, $2\cdot15$, $6\cdot5$, $6\cdot15$, $5\cdot15$. На $10$ без остатка делятся четыре произведения: $2\cdot5$, $2\cdot15$, $6\cdot5$, $6\cdot15$.
Требуется написать эффективную по времени и памяти программу. При увеличении $N$ в $k$ раз время работы программы должно увеличиваться не более чем в $k$ раз. Память, необходимая для хранения всех переменных программы, не должна превышать 1 килобайта и не должна увеличиваться с ростом $N$.
Перед текстом программы необходимо кратко описать алгоритм решения, а также указать использованный язык программирования и его версию.
Решение по шагам
8 шаговПроизведение двух чисел кратно $10$, если среди множителей можно выделить множитель $2$ и множитель $5$. Поэтому достаточно учитывать признаки делимости текущего числа на $2$ и на $5.
Числа обрабатываются слева направо. Храним только четыре счётчика: количество просмотренных чётных чисел $e$, количество чисел, кратных $5$, $f$, количество чисел, кратных $10$, $b$, и уже найденное количество подходящих пар $ans$.
Если очередное число чётное, оно образует подходящую пару с каждым предыдущим числом, кратным $5$, кроме предыдущих чисел, кратных $10$: такие числа уже имеют оба нужных свойства, и их пары следует учитывать отдельно.
Если очередное число кратно $5$, оно образует подходящую пару с каждым предыдущим чётным числом, не кратным $10$. Если число одновременно кратно $2$ и $5$, то при добавлении двух вкладов пары с предыдущими числами, кратными $10$, нужно добавить только один раз.
Удобная единая формула для очередного числа: если оно чётное и не кратно $5$, добавить $f-b$; если оно кратно $5$ и не чётное, добавить $e-b$; если оно кратно $10$, добавить $e+f-b$. После этого обновить соответствующие счётчики.
Каждое число обрабатывается один раз, поэтому время работы имеет сложность $O(N)$, а используются только несколько целочисленных переменных, поэтому дополнительная память имеет сложность $O(1)$.
Пример реализации на Python 3:
Код:
$$e = f = b = ans = 0 n = int(input()) for _ in range(n): x = int(input()) even = x % 2 == 0 five = x % 5 == 0 if even and five: ans += e + f - b elif even: ans += f - b elif five: ans += e - b if even: e += 1 if five: f += 1 if even and five: b += 1 print(ans)$$Алгоритм за $O(N)$ времени и $O(1)$ дополнительной памяти: последовательно подсчитывать подходящие пары с текущим числом, используя количества предыдущих чётных чисел, чисел, кратных $5$, и чисел, кратных $10$. Язык: Python 3.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Сохранять всю последовательность, из-за чего память зависит от $N$.
Перебирать все пары и получать сложность $O(N^2)$.
Для числа, кратного $10$, дважды учитывать пары с предыдущими числами, кратными $10$.
Не исключать случай, когда один и тот же элемент одновременно является чётным и кратен $5$.