Задача #1376
Сортировка
(С. Чайкин) В текстовом файле записан набор натуральных чисел. Рассматриваются тройки чисел, такие что элементы тройки могут являться сторонами треугольника. Необходимо определить, сколько в наборе таких троек, и наибольшую сумму элементов среди этих троек .
Входные данные
Первая строка входного файла содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее .
В ответе запишите два целых числа: сначала количество троек, затем наибольшую сумму.
Пример входного файла:
4
14
10
13
13
Ответ для приведённого примера: 4 40.
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
795608564
2994397
f = open('26.txt')
n = int(f.readline())
# отсортируем входные данные
# в порядке неубывания
a = sorted(int(x) for x in f)
count = mx = 0
# будем перебирать первые две стороны треугольника
for i in range(n-2):
r = i + 2
for l in range(i+1, n-1):
mx_side = 0
# очевидно, что a[r] > a[l] и a[r] > a[i]
# поэтому проверяем только одно неравенство
# треуголника (a < b + c)
# также очевидно, что если a[r] >= a[i] + a[l],
# треугольник не будет существовать, поэтому
# можно сразу выйти из цикла
while r < n and a[i] + a[l] > a[r]:
# так как мы ищем максимальную сумму,
# будем сохранять максимальную длину стороны
mx_side = max(mx_side, a[r])
r += 1
# все стороны a[k] (k in (l; r)) будут образовывать
# необходимый треугольник
count += r - l - 1
mx = max(mx, a[i] + a[l] + mx_side)
print(count, mx)