.08 Макс/мин, кол-во пар, сумма/разность/произведение кратно/не кратно на расстоянии

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

f = open(’A.txt’)

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

k = 3560  # Чему должна быть кратна сумма
s = 18  # Расстояние между элементами

for i in range(n):
    for j in range(i + 1, n):
        for r in range(j + 1, n):
            if j - i >= s and r - j >= s and (a[i] + a[j] + a[r]) % k == 0:
                ans += 1

print(ans)

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

f = open(’B.txt’)
n = int(f.readline())
a = [int(i) for i in f]
ans = 0

k = 3560  # Чему должна быть кратна сумма
s = 18  # Расстояние между элементами

# Список количеств чисел с определенными остатками от деления на k
# Например, под индексом 3 хранится кол-во чисел с остатком 3
nums = [0] * k

# Список из количеств пар, чья сумма имеет определенный остаток от деления на k
v = [0] * k

for i in range(s * 2, len(a)):
    # Обрабатываем элемент на расстоянии 2*s от текущего
    ost1 = a[i - s * 2] % k
    # Увеличиваем кол-во найденных элементов с таким остатком
    nums[ost1] += 1

    # Обрабатываем средний элемент - на расстоянии d от текущего
    ost2 = a[i - s] % k
    # Для каждого остатка создаём новые суммы с новым средним элементом
    # и увеличиваем количества пар с получившимися новыми остатками
    for j in range(k):
        v[(ost2 + j) % k] += nums[j]

    # Вычисляем остаток для пары в сумму к нашему числу
    ost3 = (k - (a[i] % k)) % k
    # Увеличиваем ответ на количество образованных троек
    ans += v[ost3]

print(ans)