Жауабы: Подсчёт пар с произведением
Алгоритм за $O(N)$ времени и $O(1)$ дополнительной памяти: последовательно подсчитывать подходящие пары с текущим числом, используя количества предыдущих чётных чисел, чисел, кратных $5$, и чисел, кратных $10$. Язык: Python 3.
У этого задания официального ключа нет, поэтому ответ получен в разборе және кілтпен салыстырылмаған. Нәтижені жаттамас бұрын, өтіңіз выкладки — там видно, откуда взялось каждое число.
На вход программы поступает последовательность из $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$.
Перед текстом программы необходимо кратко описать алгоритм решения, а также указать использованный язык программирования и его версию.
Где здесь ошибаются
Сохранять всю последовательность, из-за чего память зависит от $N$.
Перебирать все пары и получать сложность $O(N^2)$.
Для числа, кратного $10$, дважды учитывать пары с предыдущими числами, кратными $10$.
Не исключать случай, когда один и тот же элемент одновременно является чётным и кратен $5$.