Ответ: Подсчёт пар с делимостью
Алгоритм с очередью из пяти последних элементов, сложность O(N) по времени и O(1) по дополнительной памяти.
У этого задания официального ключа нет, поэтому ответ получен в разборе и с ключом не сверен. Перед тем как заучивать результат, пройдите выкладки — там видно, откуда взялось каждое число.
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 5 (разница в индексах элементов пары должна быть 5 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 17.
В первой строке входных данных задаётся количество чисел $N$ ($5 \leq N \leq 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 5, в которых произведение элементов кратно 17.
Пример входных данных:
8
34
2
3
5
4
6
7
17
Пример выходных данных для приведённого выше примера входных данных:
5
Пояснение: из восьми заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: $34 \cdot 6$, $34 \cdot 7$, $34 \cdot 17$, $2 \cdot 7$, $2 \cdot 17$, $3 \cdot 17$. Из них на 17 делятся 5 произведений.
Требуется написать эффективную по времени и памяти программу. Время работы должно быть не более линейным по $N$, а память для хранения переменных не должна превышать 1 килобайта и не должна увеличиваться с ростом $N$.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Где здесь ошибаются
Учитывают элементы на расстоянии менее 5.
Проверяют только текущий элемент на кратность 17 и забывают о предыдущем.
Хранят всю последовательность, нарушая требование постоянной дополнительной памяти.
Используют двойной перебор всех пар, получая сложность O(N^2).
Добавляют элемент, находящийся ровно на расстоянии 5, слишком поздно или слишком рано.