Что спрашивают
Есть 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₂, 5 | 3 + 3 > 5 | 11 |
| 3₁, 5, 6 | 3 + 5 > 6 | 14 |
| 3₂, 5, 6 | 3 + 5 > 6 | 14; другая тройка |
| 5, 6, 10 | 5 + 6 > 10 | 21 |
| 3₁, 3₂, 6 | 3 + 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))
<algorithm>
<iostream>
<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.
- Сложить три наибольших без проверки
Они могут не образовывать треугольник. Максимум периметра обновляется только у подходящих троек.