Что спрашивают

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

Найдите число допустимых троек и наибольший периметр. N ≤ 100, длина ≤ 1 000 000, хотя бы один треугольник существует. Ограничение N позволяет простой полный перебор.

Приём решения

Отсортируйте длины, сохранив все повторы. Затем переберите сочетания трёх элементов: для индексов это i < j < k. Каждая тройка отдельных отрезков будет рассмотрена ровно один раз, без перестановок.

В сортированном порядке длины a ≤ b ≤ c. Из трёх неравенств треугольника достаточно a + b > c: остальные выполнены для положительных длин автоматически. Равенство не годится — фигура вырождается в отрезок.

Для каждой подходящей тройки увеличьте счётчик и обновите максимальный периметр a + b + c. combinations работает с позициями элементов, поэтому две равные длины по разным индексам остаются разными отрезками и дают разные сочетания.

Число проверок не больше C(100, 3) = 161 700. Время O(N³), память O(N) с сортировкой и генератором сочетаний. Для существенно большего N полезен метод двух указателей за O(N²), но текущие ограничения его не требуют.

Разбор на примере

Ввод

5
6
3
10
5
3

Вывод

4 21
Разбор примера по шагам
Тройка отрезковПроверкаПериметр / решение
3₁, 3₂, 53 + 3 > 511
3₁, 5, 63 + 5 > 614
3₂, 5, 63 + 5 > 614; другая тройка
5, 6, 105 + 6 > 1021
3₁, 3₂, 63 + 3 = 6Не треугольник

Обозначим равные отрезки 3₁ и 3₂. Подходят тройки (3₁, 3₂, 5), (3₁, 5, 6), (3₂, 5, 6) и (5, 6, 10). Две тройки с длинами 3, 5, 6 различаются выбранным отрезком длины 3 и считаются отдельно. Максимальный периметр 5 + 6 + 10 = 21. Тройка 3, 3, 6 вырождена.

Код на Python и C++

Сортировка обязательна для проверки только a + b > c. Без неё сначала нужно определить наибольшую сторону либо проверить все три неравенства.

В C++ вместо combinations тройки перебирают три вложенных цикла с индексами i < j < k.

from itertools import combinations
import sys


def solve(lengths):
    count = maximum = 0
    for a, b, c in combinations(sorted(lengths), 3):
        if a + b > c:
            count += 1
            maximum = max(maximum, a + b + c)
    return count, maximum


if __name__ == '__main__':
    n, *lengths = map(int, sys.stdin.buffer.read().split())
    print(*solve(lengths))
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> lengths(n);
    for (long long& length : lengths)
        cin >> length;
    sort(lengths.begin(), lengths.end());
    long long count = 0, maximum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                long long a = lengths[i], b = lengths[j], c = lengths[k];
                if (a + b > c) {
                    count += 1;
                    maximum = max(maximum, a + b + c);
                }
            }
        }
    }
    cout << count << ' ' << maximum << endl;
}

Типичные ошибки

  • Убрать одинаковые длины

    Отрезки отдельные, даже если равны по длине. set уничтожит допустимые способы выбора.

  • Разрешить равенство в неравенстве треугольника

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

  • Перебирать перестановки

    Одна тройка не должна считаться шесть раз. Используйте i < j < k или combinations.

  • Сложить три наибольших без проверки

    Они могут не образовывать треугольник. Максимум периметра обновляется только у подходящих троек.