В текстовом файле записан набор натуральных чисел, не превышающих 
. Гарантируется, что все числа различны. Из набора нужно выбрать три числа, так чтобы чисел, больших 
было не более 
. Сколько троек, подходящих под условие задачи можно найти?
Первая строка входного файла содержит натуральное число 
— общее количество чисел в файле. Каждая из следующих 
строк содержит одно число.
Пример входного файла:
Для данного примера в ответе нужно записать 
(подходят все тройки, т.к. ни в одной из них нет больше 
-х чисел, больших 
).
Вам даны два входных файла, каждый из которых имеет описанную выше структуру. В ответе укажите два числа, ответ для файла 
и для файла 
.
Решение 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()