27.07 Макс/мин, кол-во пар, смешаное кратно/не кратно
Ошибка.
Попробуйте повторить позже
В текстовом файле записан набор натуральных чисел, не превышающих 
. Гарантируется, что все числа различны. Из
набора нужно выбрать три числа, так чтобы чисел, больших 
было не более 
. Сколько троек, подходящих под
условие задачи можно найти?
Первая строка входного файла содержит натуральное число 
— общее количество чисел в файле. Каждая из
следующих 
строк содержит одно число.
Пример входного файла:
Для данного примера в ответе нужно записать 
(подходят все тройки, т.к. ни в одной из них нет больше 
-х чисел,
больших 
).
Вам даны два входных файла, каждый из которых имеет описанную выше структуру. В ответе укажите два числа,
ответ для файла 
и для файла 
.
Решение 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] > 1000) + (a[j] > 1000) + (a[l] > 1000) <= 2:
k += 1
print(k)
Решение 2. Эффективное. Динамика
f = open("27-B.txt")
n = int(f.readline())
pairs = [0] * 3
# pairs[i] - кол-во пар на свалке, где в паре i чисел > 1000
numbers = [0] * 2
# numbers[0] - кол-во чисел на свалке, которые <= 1000
# numbers[1] - кол-во чисел на свалке, которые > 1000
ans = 0
for i in range(n):
x = int(f.readline())
if x <= 1000:
ans += pairs[0] + pairs[1] + pairs[2]
else:
ans += pairs[0] + pairs[1]
t = x > 1000 # True(1),когда x > 1000, False(0) иначе
for j in range(2):
pairs[j + t] += numbers[j]
numbers[t] += 1
print(ans)
Решение 3. Эффективное. Статика
f = open("27-B.txt")
n = int(f.readline())
more = 0
for i in range(n):
x = int(f.readline())
more += (x > 1000)
less = n - more
print(more * (more - 1) * less // 2 + more * less * (less - 1) // 2 + less * (less - 1) * (less - 2) // 6)
f.close()
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
