Тренер Игорь очень любит готовить школьников к командным олимпиадам по программированию.
Всего к нему в кружок ходит
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-той команде. Каждый ученик должен быть распределен в какую-либо команду и только в одну.
Его кружок очень популярен, и он не справляется с тем, чтобы оптимально решить эту задачу, так помогите же ему!
В первой строке вводится количество учеников
N (1 ≤
N ≤ 675,
N делится на 3).
В последующих
N строках вводятся по
N чисел: в
j-ом столбце
i-ой строки находится коэффициент сыгранности учеников под номерами
i и
j.
Выведите оптимальное разбиение на команды в виде
N/3 строк, в каждой из которых находится по 3 целых числа номера учеников в этой команде. Ученики нумеруются с единицы.
Оценкой за решение одного набора входных данных будет величина
10·(partsolution/jury_solution)3, где
jury_solution это лучшее решение среди всех участников и решения жюри, а
part_solution решение участника.
В этой задаче тесте
t = 3. Оценка за этот тест:
30 баллов.
Примеры
| № |
Входные данные |
Выходные данные |
| 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
|