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

1. Так как 29 — простое число, произведение двух целых чисел делится на 29 тогда и только тогда, когда хотя бы один из множителей делится на 29.
29∣(a⋅b)⟺29∣a  или  29∣b

2. Будем последовательно считывать числа. Для текущего числа на позиции i допустимы только элементы с индексами не больше i−4. Поэтому храним количество чисел, кратных 29, среди уже считанных элементов, которые можно образовать с текущим.

3. Чтобы не хранить всю последовательность, используем очередь из последних четырёх чисел. Перед обработкой текущего элемента число, вышедшее из очереди, становится допустимым для всех последующих элементов и добавляется в счётчик, если оно кратно 29.

4. Если текущее число кратно 29, оно образует пару с каждым допустимым ранее числом. Если оно не кратно 29, пара будет кратна 29 только с допустимым ранее числом, кратным 29. Поэтому к ответу добавляется текущий счётчик, если текущее число кратно 29, а иначе добавляется 0.

5. Алгоритм работает за время O(N) и использует O(1) дополнительной памяти. Пример программы на Python 3:

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