Олимпиадный тренинг

Задача . C2 (2023). Разбиение на команды


Задача

Темы:
Тренер Игорь очень любит готовить школьников к командным олимпиадам по программированию.
Всего к нему в кружок ходит N (N делится на 3) школьников, и, так как Игорь уже довольно опытный тренер, то для каждой пары школьников a и b он знает коэффициент сыгранности Ca,b этих двух школьников. По его наблюдениям, если в одной команде находятся ученики под номерами a, b, c, успех их команды можно будет выразить как Ca,b · Cb,c · Ca,c. Игорю будет приятно, если как можно больше школьников успешно выступят на предстоящей Межгалактической Командной Олимпиаде Школьников по Программированию (МКОШП), и он хочет максимизировать суммарный успех составленных команд.
Иными словами, Игорь хочет максимизировать сумму Cai,bi · Cbi,ci · Cai,ci по всем i от 1 до N/3, где ai, bi, ci номера учеников в i-той команде. Каждый ученик должен быть распределен в какую-либо команду и только в одну.
Его кружок очень популярен, и он не справляется с тем, чтобы оптимально решить эту задачу, так помогите же ему!

В первой строке вводится количество учеников (1 ≤ N ≤ 675, N делится на 3).
В последующих N строках вводятся по N чисел: в j-ом столбце i-ой строки находится коэффициент сыгранности учеников под номерами i и j.
Выведите оптимальное разбиение на команды в виде N/3 строк, в каждой из которых находится по 3 целых числа номера учеников в этой команде. Ученики нумеруются с единицы.
Оценкой за решение одного набора входных данных будет величина 10·(partsolution/jury_solution)3, где jury_solution это лучшее решение среди всех участников и решения жюри, а part_solution решение участника.
В этой задаче t = 7. Оценка за этот тест: 70 баллов. 
Примеры
Входные данные Выходные данные
1
1
6
0 1 1 1 1 2
1 0 3 1 1 1
1 3 0 1 1 1
1 1 1 0 1 1
1 1 1 1 0 1
2 1 1 1 1 0
1 6 4
2 3 5

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python2
Комментарий учителя