Задача №111531. Футбол
Футбольный клуб «Инжир» не имеет проблем с финансированием, поэтому приобрел N полевых игроков. После долгих месяцев тренировок и тестов тренерский коллектив подробно изучил каждого игрока и собирается выбрать оптимальный стартовый состав.
Каждый игрок характеризуется тремя целыми неотрицательными числами: di — умение играть в защите, mi — умение играть в полузащите и ai — умение играть в нападении. Играть было решено по схеме 5-3-2. Это означает, что в основном составе будет 5 игроков защиты, 3 полузащитника и 2 нападающих. Цель тренерского штаба — выбрать 10 игроков так, чтобы сумма соответствующих умений была максимальна (для игрока обороны значение имеет только его умение играть в защите, аналогично для других позиций). Разумеется, каждый игрок может играть не более чем на одной позиции. Ваша задача — помочь тренерскому штабу подобрать оптимальный состав.
В первой строке входного файла находится одно целое число N — количество игроков в клубе. Следующие N строк файла содержат по три целых числа каждая di, mi и ai — умения футболиста с номером i играть в обороне, полузащите и нападении соответственно.
Выходной файл должен содержать ровно три строки. Первая строка должна содержать пять чисел — номера игроков обороны. Вторая строка должна содержать ровно три числа — номера игроков полузащиты. Третья строка должна содержать ровно два числа — номера игроков нападения. Если оптимальных ответов несколько, можно вывести любой.
10
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9
8 9 10
9 10 1
10 1 2
10 9 8 7 6
3 4 5
1 2
10
1 5 1
3 2 2
3 3 5
2 1 3
4 4 5
2 0 2
1 1 1
4 5 1
1 3 3
4 5 4
10 5 2 6 7
1 8 9
3 4
Тесты состоят из пяти групп. Во всех группах 0 ≤ di, mi, ai ≤ 107.
- Тесты 1–2, из условия, оцениваются в 0 баллов.
- В тестах этой группы N = 10. Эта группа оценивается в 20 баллов, баллы начисляются только при прохождении всех тестов группы.
- В тестах этой группы 10 ≤ N ≤ 40. Эта группа также оценивается в 20 баллов, они начисляются только при прохождении всех тестов группы.
- В тестах этой группы 10 ≤ N ≤ 10 000. Эта группа также оценивается в 20 баллов, они начисляются только при прохождении всех тестов группы.
- 10 ≤ N ≤ 500 000. Баллы за тесты этой группы начисляются только при прохождении всех тестов всех предыдущих групп. Некоторые тесты этой группы объединяются в подгруппы, тесты за каждую подгруппу ставятся только при прохождении всех тестов подгруппы.