Решение: Пары на расстоянии пять
На вход программы поступает последовательность из $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$.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение по шагам
6 шаговПроизведение двух целых чисел делится на 11, если хотя бы один из множителей делится на 11, поскольку 11 является простым числом.
Нельзя хранить всю последовательность. Будем обрабатывать числа последовательно и хранить только количество элементов, которые уже разрешено использовать в паре с текущим элементом. Для позиции $i$ разрешены позиции не более $i-5$, поэтому перед обработкой текущего числа добавляется элемент с индексом $i-5$.
Храним два счётчика: количество разрешённых элементов, кратных 11, и количество разрешённых элементов, не кратных 11. Если текущее число кратно 11, оно образует подходящую пару с каждым разрешённым элементом. Иначе оно образует подходящую пару только с разрешёнными элементами, кратными 11.
Для ограничения памяти достаточно хранить последние пять чисел в циклическом буфере. Каждый элемент добавляется в счётчики ровно один раз и обрабатывается ровно один раз, поэтому время работы имеет сложность $O(N)$, а дополнительная память — $O(1)$.
Программа на Python 3.11:
from collections import deque
n = int(input())
window = deque()
count_div11 = 0
count_other = 0
answer = 0
for i in range(n):
x = int(input())
if len(window) == 5:
old = window.popleft()
if old % 11 == 0:
count_div11 += 1
else:
count_other += 1
if x % 11 == 0:
answer += count_div11 + count_other
else:
answer += count_div11
window.append(x)
print(answer)
Алгоритм работает за $O(N)$ времени и использует $O(1)$ дополнительной памяти; для приведённого примера программа выводит 5.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Учитывают элементы на расстоянии менее 5.
Считают произведение кратным 11 только тогда, когда оба множителя кратны 11.
Добавляют текущий элемент в счётчики до подсчёта пар, из-за чего он может образовать пару сам с собой.
Хранят всю последовательность и тем самым нарушают требование по памяти.
Используют двойной цикл и получают сложность $O(N^2)$.