Решение: Пары на расстоянии четыре
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4: разница в индексах элементов пары должна быть 4 или больше, порядок элементов в паре неважен. Необходимо определить количество таких пар, для которых произведение элементов делится на 29.
В первой строке входных данных задаётся количество чисел $N$ ($4 \le N \le 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше 4, в которых произведение элементов кратно 29.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел $N$ в $k$ раз время работы программы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом $N$.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение по шагам
6 шаговТак как 29 — простое число, произведение двух целых чисел делится на 29 тогда и только тогда, когда хотя бы один из множителей делится на 29.
$$29 \mid (a \cdot b) \Longleftrightarrow 29 \mid a \;\text{или}\; 29 \mid b$$Будем последовательно считывать числа. Для текущего числа на позиции $i$ допустимы только элементы с индексами не больше $i-4$. Поэтому храним количество чисел, кратных 29, среди уже считанных элементов, которые можно образовать с текущим.
Чтобы не хранить всю последовательность, используем очередь из последних четырёх чисел. Перед обработкой текущего элемента число, вышедшее из очереди, становится допустимым для всех последующих элементов и добавляется в счётчик, если оно кратно 29.
Если текущее число кратно 29, оно образует пару с каждым допустимым ранее числом. Если оно не кратно 29, пара будет кратна 29 только с допустимым ранее числом, кратным 29. Поэтому к ответу добавляется текущий счётчик, если текущее число кратно 29, а иначе добавляется 0.
Алгоритм работает за время $O(N)$ и использует $O(1)$ дополнительной памяти. Пример программы на Python 3:
from collections import deque
n = int(input())
last_four = deque()
count29 = 0
answer = 0
for _ in range(n):
x = int(input())
if len(last_four) == 4:
old = last_four.popleft()
if old % 29 == 0:
count29 += 1
if x % 29 == 0:
answer += count29
last_four.append(x)
print(answer)
Язык: Python 3. Алгоритм: однопроходное считывание последовательности, очередь последних четырёх элементов и счётчик доступных элементов, кратных 29. Сложность по времени — $O(N)$, дополнительная память — $O(1)$. Программа приведена в решении.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверять все пары и получать квадратичную сложность $O(N^2)$.
Считать допустимыми элементы, находящиеся на расстоянии 3.
Забыть, что произведение кратно 29, если хотя бы один множитель кратен 29.
Добавлять в счётчик текущий элемент до проверки пар с ним.
Хранить всю последовательность, нарушая требование о постоянном объёме памяти.