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

Просмотров 8 Комментарии 0

В текстовом файле записан набор натуральных чисел, не превышающих $108$ . Гарантируется, что все числа различны. Из набора нужно выбрать три числа, произведение которых делится на $5$ . Сколько троек, подходящих под условие задачи можно найти?

Первая строка входного файла содержит натуральное число $N$ — общее количество чисел в файле. Каждая из следующих $N$ строк содержит одно число.

Пример входного файла:

$4$

$5$

$8$

$14$

$11$

Для данного примера в ответе нужно записать $3$ (подходят следующие тройки ( $5,8,14$ ), ( $5,8,11$ ), ( $5,11,14$ )).

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

Решение 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]) % 5 == 0:
                k += 1
print(k)

Решение 2. Эффективное. Динамика

f = open("27-A.txt")
n = int(f.readline())
numbers = [0] * 6
pairs = [0] * 6
ans = 0

for i in range(n):
    x = int(f.readline())

    for j in range(1, 6):
        if 5 % j == 0:
            if x * j % 5 == 0:
                ans += pairs[j]

    for j in range(5, 0, -1):
        for k in range(5, 0, -1):
            if x * j % k == 0 and 5 % j == 0 and 5 % k == 0:
                pairs[k] += numbers[j]
                break

    for j in range(5, 0, -1):
        if x % j == 0 and 5 % j == 0:
            numbers[j] += 1
            break

print(ans)

Решение 3. Эффективное. Статика

f = open("27-B.txt")
n = int(f.readline())
kr5 = 0
for i in range(n):
    x = int(f.readline())
    kr5 += (x % 5 == 0)

nekr = n - kr5

ans = (kr5 * nekr * (nekr - 1) // 2 +
        nekr * kr5 * (kr5 - 1) // 2 +
        kr5 * (kr5 - 1) * (kr5 - 2) // 6)

print(ans)

Ответ: 3896 81078489940921