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