Дано натуральное число N, затем N натуральных чисел. Требуется найти количество пар чисел, чья сумма будет кратна 10. Парой считаются два элемента, расстояние между которыми равно 3 и более (т.е. разница между их индексами >= 3).
В первой строке входных данных задаётся количество чисел N (
N 
). В каждой из последующих N строк записано одно целое положительное число, строго меньшее 10000.
Пример входных данных:
Подходящими парами будут являться: (10, 40), (10, 50), (10, 60), (10, 70), (20, 50), (20, 60), (20, 70), (30, 60), (30, 70), (40, 70) и ответом будет являться 10.
В ответ укажите два числа через пробел: сначала искомое значение для файла A, затем для файла B.
Переборное решение:
f = open(’1_A.txt’)
n = int(f.readline())
a = [int(i) for i in f]
cnt = 0
for i in range(n):
for j in range(i + 1, n):
if (a[i] + a[j]) % 10 == 0 and j - i >= 3:
cnt += 1
print(cnt)
Эффективное решение:
f = open(’1_B.txt’)
n = int(f.readline())
a = [int(i) for i in f]
cnt = 0
k = 10 # Чему должна быть кратна сумма
s = 3 # Расстояние между элементами
# Список количеств чисел с определенными остатками от деления на k
# Например, под индексом 3 хранится кол-во чисел с остатком 3
nums = [0] * k
for i in range(s, n):
# Считаем остаток от деления первого числа пары на k
ost1 = a[i - s] % k
# Увеличиваем кол-во чисел с найденным остатком
nums[ost1] += 1
# Считаем остаток, который должен быть у числа,
# которое можно поставить в пару с текущим
ost2 = (k - (a[i] % k)) % k
# Увеличиваем ответ на количество образованных пар
cnt += nums[ost2]
print(cnt)