Задача №3882. Собрать треугольник
Вы по-прежнему работаете под руководством д.б.н., проф. О.Б. Ломова и изучаете интеллект обезьян. Ваши подопечные уже очень далеко ушли от столь элементарной задачи, как сбор квадрата. Теперь вы работаете над тем, чтобы обучить их намного более сложной задаче. Вы по-прежнему даёте обезьянам набор из \(N\) палочек, но на этот раз вы хотите, чтобы они собрали из этих палочек треугольник.
Конечно, решить эту задачу в элементарном варианте — выбрать три палочки и собрать из них треугольник — ваши подопечные могут без каких-либо проблем; вы же хотите их обучить, чтобы они собирали один большой треугольник из всех выданных им палочек сразу. Таким образом, они должны разбить палочки на три группы так, чтобы, сложив палочки каждой группы в один большой отрезок, получить три отрезка, из которых можно собрать треугольник. Полученный треугольник должен быть невырожденным, т.е. его площадь должна быть строго больше нуля.
Как и в прошлый раз, вам понадобилась программа, которая определит, разрешима ли задача для данного набора палочек.
На первой строке входного файла находится одно натуральное число \(N\) — количество палочек в наборе (\(1\leq N \leq 16\,000\)). На второй строке находятся \(N\) натуральных чисел — длины палочек. Гарантируется, что суммарная длина палочек не превосходит \(100\,000\,000\).
Если решения не существует, то в первую строку выходного файла выведите одно слово “no”
(без кавычек). В противном случае в первую строку выведите одно слово “yes”, а в
следующие три строки выведите какой-нибудь способ собрать треугольник из данных палочек. Каждая
из этих трёх строк должна описывать очередную сторону получающегося треугольника: в каждой строке
сначала должно идти количество палочек, из которых состоит эта сторона, а потом длины этих палочек.
Каждую палочку, конечно, можно использовать только один раз.
Если есть несколько способов собрать треугольник из данных палочек, выведите любой.
5 1 2 3 4 5
yes 2 4 3 1 5 2 1 2
5 1 2 3 4 100
no