Задание 26 ЕГЭ по информатике

Question

В текстовом файле записан набор натуральных чисел. Рассматриваются тройки чисел, такие что элементы тройки могут являться сторонами треугольника. Необходимо определить, сколько в наборе таких троек, и наибольшую сумму элементов среди этих троек .
Входные данные
Первая строка входного файла содержит целое число $N$ – общее количество чисел в наборе. Каждая из следующих $N$ строк содержит одно число, не превышающее $10^6$.
В ответе запишите два целых числа: сначала количество троек, затем наибольшую сумму.
Типовой пример организации входных данных
4
14
10
13
13
Ответ для приведённого примера: 4 40.
Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/10072_26.txt

Accepted Answer

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)

Задание 26 ЕГЭ по информатике

Задания на обработку данных с помощью сортировки