Задача к ЕГЭ по информатике на тему «Макс/мин, кол-во пар, сумма/разность/произведение кратно/не кратно на расстоянии» №2

На вход подаётся последовательность из $9 < n ≤ 100000$ натуральных чисел, каждое из которых не больше $1000$ . Напишите программу, вычисляющую количество пар элементов последовательности, сумма которых делится на $7$ , произведение не кратно $15$ , и хотя бы одно число из пары больше $50$ , находящихся на расстоянии не меньше $8$ .

В первой строке входных данных задаётся количество чисел $N$ $(1 ≤ N ≤ 100000)$ . В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее $10$ $000$ .

В ответе укажите два числа через пробел: сначала значение искомой суммы для файла $A$ , затем для файла $B$ .

Пример входных и выходных данных:


Входные данные	Выходные данные

10	1
100
85
94
49
92
29
48
27
61
29

Переборное решение:

f = open("10_A.txt")
n = int(f.readline())
a = []
for i in range(n):
    a.append(int(f.readline()))
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        if (a[i] > 50 or a[j] > 50) and (a[i] + a[j]) % 7 == 0 and (a[i] * a[j]) % 15 != 0 and j - i >= 8:
            cnt += 1
print(cnt)

Эффективное решение:

f = open(’10_B.txt’)

s = 8  # Расстояние между элементами
k = 7  # Чему должна быть кратна сумма
p = 15  # Чему не должно быть кратно произведение
d = [15, 5, 3, 1]

n = int(f.readline())
a = [int(i) for i in f]

# Список с количествами чисел, удовлетворяющих определенным условием
# Индексы числа nums[x][y][z] обозначают следующее:
# x - больше ли число чем 50 (1 - да, 0 - нет)
# y - максимальный делитель p, которому кратно число
# z - остаток от деления числа на k
nums = [[[0] * k for _ in range(p + 1)] for _ in range(2)]
cnt = 0

for i in range(s, n):
    # Находим остаток первого числа пары
    ost1 = a[i - s] % k

    # Ищем максимальный делитель, которому кратно число
    for j in d:
        if a[i - s] % j == 0:
            # Увеличиваем количество чисел с такими характеристиками
            nums[int(a[i - s] > 50)][j][ost1] += 1
            break

    # Вычисляем остаток от деления на k числа-пары для x
    ost2 = (k - (a[i] % k)) % k

    # Перебираем все возможные делители и ищем те, при которых произведение
    # не будет кратно 15
    for j in d:
        if (a[i] * j) % 15 != 0:
            # Увеличиваем ответ на количество пар с x, сумма которых будет кратна k,
            # где первое число точно больше 50












































































































































































































            cnt += nums[1][j][ost2]
            # Если a[i] больше 50, то его можно поставить также в пару с числами меньше 50
            if a[i] > 50:
                cnt += nums[0][j][ost2]

print(cnt)

Ответ: 30 5715135