В текстовом файле записан набор натуральных чисел, не превышающих 
. Гарантируется, что все числа различны. Из набора нужно выбрать три числа, произведение которых делится на 
. Сколько троек, подходящих под условие задачи можно найти?
Первая строка входного файла содержит натуральное число 
— общее количество чисел в файле. Каждая из следующих 
строк содержит одно число.
Пример входного файла:
Для данного примера в ответе нужно записать 
(подходят следующие тройки (
), (
), (
)).
Вам даны два входных файла, каждый из которых имеет описанную выше структуру. В ответе укажите два числа, ответ для файла 
и для файла 
.
Решение 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]) % 8 == 0:
k += 1
print(k)
Решение 2. Эффективное. Динамика
f = open("27-B.txt")
n = int(f.readline())
numbers = [0] * 9
pairs = [0] * 9
ans = 0
for i in range(n):
x = int(f.readline())
for j in range(1, 9):
if 8 % j == 0:
if x * j % 8 == 0:
ans += pairs[j]
for j in range(8, 0, -1):
for k in range(8, 0, -1):
if x * j % k == 0 and 8 % j == 0 and 8 % k == 0:
pairs[k] += numbers[j]
break
for j in range(8, 0, -1):
if x % j == 0 and 8 % j == 0:
numbers[j] += 1
break
print(ans)