Поскольку соревнования по спортивному программированию часто проходит в остановке острой, напряжённой и упорной борьбы, правительство Берляндии поручило национальной федерации этого вида спорта организовывать и проводить все олимпиады по информатике в стране.
По мнению главы федерации, важнейшей характеристикой спортсмена (а теперь и программиста) является его вес. Поэтому атлетов распределяют на весовые категории, соперники в которых сравнительно равны по физическим возможностям.
Для первой олимпиады, проводимой под эгидой федерации, было принято решение разделить всех 1000 участников всего лишь на три весовые категории (лёгкую, среднюю и тяжёлую).
На церемонии открытия олимпиады все программисты одной весовой категории выходят на специальный помост для приветствия и фотографирования. Важнейшей характеристикой такого помоста является прочность — он должен выдержать вес всех поднявшихся на него атлетов. Помогите организаторам определить границы весовых категорий таким образом, чтобы наибольший суммарный вес борцов из одной весовой категории был наименьшим.
Найдите такое подходящее разбиение участников по весовым категориям, чтобы суммы весов первых A спортсменов (с наименьшим весом), следующих B спортсменов и последних C спортсменов (с наибольшим весом) из предложенного списка отличались как можно меньше. При этом спортсмены с одинаковым весом должны находиться в одной весовой категории.
Входные данные для этой задачи находятся в файле электронной таблицы в виде неубывающего списка натуральных чисел.
В качестве ответа запишите три числа A, B, C, дающие в сумме 1000.
Баллы будут начисляться только за такие ответы, в которых спортсмены с одинаковым весом целиком попадают в одну весовую категорию. При этом чем меньше будет наибольший суммарный вес участников одной весовой категории, тем больше баллов получит решение.
Замечание
Пример: в соревновании принимают участие 10 спортсменов и их веса равны 10, 20, 30, 30, 40, 40, 50, 50, 60, 100
Назначим шесть первых программистов в лёгкую весовую категорию (их суммарный вес 170), двух следующих — в среднюю (100), двух последних — в тяжёлую (160). Тогда помост должен выдерживать вес 170
Такой же результат даст ещё одно разбиение: шесть первых спортсменов назначить в лёгкую весовую категорию (170), трёх следующих — в среднюю (160), последнего — в тяжёлую (100). Если пять первых программистов назначить в лёгкую весовую категорию (130), трёх следующих — в среднюю (140), двух последних — в тяжёлую (160), то, на первый взгляд, можно достигнуть ещё более оптимальной прочности помоста — 160
Но тогда пятый и шестой участники (имеющие равный вес) окажутся в разных весовых категориях, что является нарушением спортивного принципа. Ответом в этом примере будут числа 6, 2, 2 или 6, 3, 1
