В текстовом файле записан набор натуральных чисел, не превышающих 
. Гарантируется, что все числа различны. Из набора нужно выбрать три числа, сумма которых делится на 
. Сколько троек, подходящих под условие задачи можно найти?
Первая строка входного файла содержит натуральное число 
— общее количество чисел в файле. Каждая из следующих 
строк содержит одно число.
Пример входного файла:
В данном случае есть четыре подходящие тройки: 
(сумма 
); 
(сумма 
); 
(сумма 
) и 
(сумма 
). В ответе надо записать число 
.
Вам даны два входных файла, каждый из которых имеет описанную выше структуру. В ответе укажите два числа, ответ для файла 
и для файла 
.
Решение 1. Неэффективное
f = open("27-A.txt")
n = int(f.readline())
a = []
for i in range(n):
a.append(int(f.readline()))
k = 0
for i in range(n):
for j in range(i + 1, n):
for l in range(j + 1, n):
if (a[i] + a[j] + a[l]) % 3 == 0:
k += 1
print(k)
Решение 1. Эффективное. Динамика
f = open(’15.txt’)
n = int(f.readline())
a = [int(i) for i in f]
k = 3
# Количества чисел с определенным остатком от деления
t = [0] * k
# Количества пар чисел, чья сумма обладает определенным остатком от деления
v = [0 for i in range(k)]
cnt = 0
for i in range(2, len(a)):
# Обрабатываем элемент на расстоянии 2 от текущего (через один слева)
ost1 = a[i - 2] % k
# Увеличиваем количество элементов с таким остатком
t[ost1] += 1
# Обрабатываем средний элемент - на расстоянии 1 от текущего (слева)
ost2 = a[i - 1] % k
# Средний элемент образует пары со всеми ранее встреченными элементами
# С элементом с каждым остатком образуется пара с суммой с новым остатком
# Увеличиваем количество пар на количество элементов с таким остатком,
# с которым мы составили пару
for j in range(k):
v[(j + ost2) % k] += t[j]
# Вычисляем остаток для пары в сумму к нашему числу для образования тройки
ost3 = (k - (a[i] % k)) % k
# Увеличиваем счётчик на количество пар с таким остатком
cnt += v[ost3]
print(cnt)