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

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

1. Для каждого числа достаточно знать два булевых признака: делится ли оно на 2 и делится ли оно на 3. Это определяет один из четырёх типов числа.

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

3. После подсчёта подходящих предыдущих чисел увеличить счётчик типа текущего числа. Так каждая пара учитывается ровно один раз — в момент обработки второго элемента пары.
O(N) по времени и O(1) по дополнительной памяти

4. Эталонная реализация на Python 3.11:

5. from sys import stdin n = int(stdin.readline()) cnt = [[0, 0], [0, 0]] answer = 0 for _ in range(n):
x = int(stdin.readline()) d2 = int(x % 2 == 0) d3 = int(x % 3 == 0) for p2 in range(2):
for p3 in range(2):
if (d2 or p2) and (d3 or p3):
answer += cnt[p2][p3] cnt[d2][d3] += 1 print(answer)