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