.06 Макс/мин, кол-во пар, произведение кратно/не кратно
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В текстовом файле записан набор натуральных чисел, не превышающих 
. Гарантируется, что все числа различны. Из
набора нужно выбрать три числа, произведение которых делится на 
. Сколько троек, подходящих под условие задачи
можно найти?
Первая строка входного файла содержит натуральное число 
— общее количество чисел в файле. Каждая из
следующих 
строк содержит одно число.
Пример входного файла:
Для данного примера в ответе нужно записать 
(подходят следующие тройки (
), (
),
(
)).
Вам даны два входных файла, каждый из которых имеет описанную выше структуру. В ответе укажите два числа,
ответ для файла 
и для файла 
.
Решение 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)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
