Решение: Пары на расстоянии три
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3: разница в индексах элементов пары должна быть 3 или более, порядок элементов в паре неважен. Необходимо определить количество таких пар, для которых произведение элементов делится на 13.
В первой строке входных данных задаётся количество чисел $N$ ($3 \leq N \leq 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше 3, в которых произведение элементов кратно 13.
Пример входных данных:
6
26
2
3
5
4
13
Пример выходных данных для приведённого выше примера входных данных:
5
Из шести заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: $26 \cdot 5$, $26 \cdot 4$, $26 \cdot 13$, $2 \cdot 4$, $2 \cdot 13$, $3 \cdot 13$. Из них на 13 делятся 5 произведений.
Требуется написать эффективную по времени и памяти программу для решения задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел $N$ в $k$ раз время работы программы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом $N$.
Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
Решение по шагам
7 шаговБудем рассматривать элементы последовательности слева направо. Для элемента с индексом $i$ допустимы только элементы с индексами не больше $i-3$.
$$j \leq i-3$$При обработке очередного элемента добавляем в группу допустимых элемент, который находится ровно на расстоянии 3. Храним количество всех добавленных элементов и количество элементов, кратных 13.
Если текущий элемент кратен 13, его произведение с каждым допустимым элементом делится на 13. Поэтому к ответу добавляется количество всех допустимых элементов.
Если текущий элемент не кратен 13, произведение делится на 13 только с допустимыми элементами, кратными 13. К ответу добавляется их количество.
Каждый элемент обрабатывается один раз, поэтому время работы имеет линейную сложность $O(N)$. Хранится только очередь из последних трёх чисел и несколько счётчиков, поэтому дополнительная память не зависит от $N$ и имеет сложность $O(1)$.
Программа на Python 3.11:
from collections import deque
n = int(input())
last = deque()
total = 0
multiple13 = 0
answer = 0
for _ in range(n):
x = int(input())
if len(last) == 3:
old = last.popleft()
total += 1
if old % 13 == 0:
multiple13 += 1
if x % 13 == 0:
answer += total
else:
answer += multiple13
last.append(x)
print(answer)
Алгоритм работает за $O(N)$ по времени и за $O(1)$ по дополнительной памяти. Приведённая программа на Python 3.11 подсчитывает количество подходящих пар без хранения всей последовательности.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Учитывать элементы на расстоянии 1 или 2, хотя допустимое расстояние должно быть не меньше 3.
Добавлять элемент в множество допустимых до проверки текущего элемента, из-за чего учитывается расстояние 2.
Проверять только случай, когда оба числа делятся на 13, хотя достаточно делимости хотя бы одного множителя.
Хранить всю последовательность и использовать двойной цикл, получая сложность $O(N^2)$.