Решение: Пары чисел, кратные 23
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3: разница в индексах элементов пары должна быть 3 или более, порядок элементов в паре неважен. Необходимо определить количество таких пар, для которых произведение элементов делится на 23.
В первой строке входных данных задаётся количество чисел $N$ ($3 \leq N \leq 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее 10 000. Программа должна вывести одно число — количество подходящих пар.
Требуется написать эффективную по времени и памяти программу. Программа считается эффективной по времени, если при увеличении $N$ в $k$ раз время её работы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память для хранения всех переменных не превышает 1 килобайта и не увеличивается с ростом $N$.
Перед текстом программы кратко опишите алгоритм решения, укажите использованный язык программирования и его версию.
Решение по шагам
6 шаговДля пары элементов произведение кратно 23 тогда и только тогда, когда хотя бы один элемент пары кратен 23.
При чтении элемента с индексом $i$ допустимыми предыдущими являются элементы с индексами не больше $i-3$. Поэтому перед обработкой текущего элемента в счётчик добавляется элемент, прочитанный три позиции назад.
Пусть count23 — количество добавленных допустимых предыдущих элементов, кратных 23, а available — общее количество добавленных допустимых элементов. Если текущий элемент кратен 23, он образует подходящую пару с каждым из available элементов. Иначе он образует подходящую пару только с count23 элементами.
После обработки текущего элемента его значение сохраняется в очереди из последних трёх элементов, чтобы через три шага добавить его в множество допустимых предыдущих элементов. Используется постоянное количество переменных, поэтому память не зависит от $N$.
Программа работает за $O(N)$ по времени и за $O(1)$ по дополнительной памяти.
Один из вариантов реализации на Python 3:
Алгоритм с постоянной памятью: для каждого числа учитывать элементы, прочитанные не менее чем за три позиции до него; подсчитывать пары за $O(N)$.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Учитывать элементы, находящиеся на расстоянии 1 или 2 позиций.
Добавлять текущий элемент в счётчик допустимых элементов до подсчёта пар с ним.
Считать только пары двух чисел, кратных 23, хотя достаточно кратности 23 одного множителя.
Хранить всю последовательность, нарушая требование по памяти.
Использовать двойной цикл и получить сложность $O(N^2)$.