Задача 21 из 21

Треугольники из отрезков

Время 2 с · память 256 МБ

Имеется NN отрезков, длина каждого — натуральное число. Из трёх отрезков можно составить треугольник, если сумма длин двух меньших из них больше длины третьего. Отрезки одинаковой длины считаются разными.

Определите количество способов выбрать три отрезка, из которых можно составить треугольник, и наибольший периметр такого треугольника. Способы, которые различаются только порядком выбора отрезков, считаются одним способом.

Входные данные

В первой строке находится число NN — количество отрезков (натуральное число, не превышающее 100). В каждой из следующих NN строк находится длина одного отрезка — натуральное число, не превышающее 1 000 0001\,000\,000.

Длины идут в произвольном порядке и могут повторяться. Гарантируется, что хотя бы один треугольник составить можно.

Выходные данные

Выведите два целых числа: сначала количество способов, затем наибольший периметр.

Примеры

Ввод 1
4
4
6
7
10
Вывод 1
3 23
Ввод 2
4
1
2
3
4
Вывод 2
1 9

Примечание

В первом примере треугольник можно составить из отрезков с длинами 4, 6, 7; 4, 7, 10; 6, 7, 10. Периметры этих треугольников равны 17, 21 и 23. Во втором примере подходит только тройка 2, 3, 4: в тройках 1, 2, 3 и 1, 3, 4 сумма двух меньших длин равна третьей.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче