Задание 27 ЕГЭ по информатике · ED6EB9

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3: разница в индексах элементов пары должна быть 3 или более, порядок элементов в паре неважен. Необходимо определить количество таких пар, для которых произведение элементов делится на 13.
В первой строке входных данных задаётся количество чисел N (3≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше 3, в которых произведение элементов кратно 13.
Пример входных данных:
6
26
2
3
5
4
13
Пример выходных данных для приведённого выше примера входных данных:
5
Из шести заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 26⋅5, 26⋅4, 26⋅13, 2⋅4, 2⋅13, 3⋅13. Из них на 13 делятся 5 произведений.
Требуется написать эффективную по времени и памяти программу для решения задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.

1. Будем рассматривать элементы последовательности слева направо. Для элемента с индексом i допустимы только элементы с индексами не больше i−3.
j≤i−3

2. При обработке очередного элемента добавляем в группу допустимых элемент, который находится ровно на расстоянии 3. Храним количество всех добавленных элементов и количество элементов, кратных 13.

3. Если текущий элемент кратен 13, его произведение с каждым допустимым элементом делится на 13. Поэтому к ответу добавляется количество всех допустимых элементов.

4. Если текущий элемент не кратен 13, произведение делится на 13 только с допустимыми элементами, кратными 13. К ответу добавляется их количество.

5. Каждый элемент обрабатывается один раз, поэтому время работы имеет линейную сложность O(N). Хранится только очередь из последних трёх чисел и несколько счётчиков, поэтому дополнительная память не зависит от N и имеет сложность O(1).

6. Программа на Python 3.11:

7. 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)