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

1. Произведение двух чисел кратно 10, если среди множителей можно выделить множитель 2 и множитель 5. Поэтому достаточно учитывать признаки делимости текущего числа на 2 и на 5.

2. Числа обрабатываются слева направо. Храним только четыре счётчика: количество просмотренных чётных чисел e, количество чисел, кратных 5, f, количество чисел, кратных 10, b, и уже найденное количество подходящих пар ans.

3. Если очередное число чётное, оно образует подходящую пару с каждым предыдущим числом, кратным 5, кроме предыдущих чисел, кратных 10: такие числа уже имеют оба нужных свойства, и их пары следует учитывать отдельно.

4. Если очередное число кратно 5, оно образует подходящую пару с каждым предыдущим чётным числом, не кратным 10. Если число одновременно кратно 2 и 5, то при добавлении двух вкладов пары с предыдущими числами, кратными 10, нужно добавить только один раз.

5. Удобная единая формула для очередного числа: если оно чётное и не кратно 5, добавить f−b; если оно кратно 5 и не чётное, добавить e−b; если оно кратно 10, добавить e+f−b. После этого обновить соответствующие счётчики.

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

7. Пример реализации на Python 3:

8. Код:
e = f = b = ans = 0
n = int(input())
for _ in range(n):
x = int(input())
even = x % 2 == 0
five = x % 5 == 0

if even and five:
ans += e + f - b
elif even:
ans += f - b
elif five:
ans += e - b

if even:
e += 1
if five:
f += 1
if even and five:
b += 1

print(ans)