Ответ: Пары на расстоянии четыре
Язык: Python 3. Алгоритм: однопроходное считывание последовательности, очередь последних четырёх элементов и счётчик доступных элементов, кратных 29. Сложность по времени — $O(N)$, дополнительная память — $O(1)$. Программа приведена в решении.
У этого задания официального ключа нет, поэтому ответ получен в разборе и с ключом не сверен. Перед тем как заучивать результат, пройдите выкладки — там видно, откуда взялось каждое число.
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4: разница в индексах элементов пары должна быть 4 или больше, порядок элементов в паре неважен. Необходимо определить количество таких пар, для которых произведение элементов делится на 29.
В первой строке входных данных задаётся количество чисел $N$ ($4 \le N \le 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше 4, в которых произведение элементов кратно 29.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел $N$ в $k$ раз время работы программы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом $N$.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Где здесь ошибаются
Проверять все пары и получать квадратичную сложность $O(N^2)$.
Считать допустимыми элементы, находящиеся на расстоянии 3.
Забыть, что произведение кратно 29, если хотя бы один множитель кратен 29.
Добавлять в счётчик текущий элемент до проверки пар с ним.
Хранить всю последовательность, нарушая требование о постоянном объёме памяти.