Codeforces Round 604 (Div. 1) |
---|
Закончено |
Футбольная лига недавно стартовала в Красивой долине. Всего $$$n$$$ команд участвует в этой лиге. Пронумеруем их для удобства целыми числами от $$$1$$$ до $$$n$$$.
Всего будет проведено ровно $$$\frac{n(n-1)}{2}$$$ матчей: каждая команда будет играть со всеми оставшимися командами ровно по одному разу. В каждом матче всегда есть победившая и проигравшая команда, ничьих не бывает.
После того, как все матчи будут сыграны, организаторы посчитают количество красивых троек. Тройка команд $$$(A, B, C)$$$ называется красивой, если команда $$$A$$$ победила команду $$$B$$$, команда $$$B$$$ победила команду $$$C$$$ и команда $$$C$$$ победила команду $$$A$$$. Мы рассматриваем только тройки различных команд, порядок команд внутри тройки имеет значение.
Красотой лиги назовем количество красивых троек.
В данный момент, $$$m$$$ матчей уже было проведено и их результаты уже известны.
Какая максимальная красота лиги может быть в итоге, после проведения оставшихся матчей? Также найдите возможные результаты оставшихся $$$\frac{n(n-1)}{2} - m$$$ матчей, при которых красота лиги максимально возможная.
В первой строке находится два целых числа $$$n, m$$$ ($$$3 \leq n \leq 50, 0 \leq m \leq \frac{n(n-1)}{2}$$$) — количество команд в футбольной лиге и количество матчей, которое уже проведено.
Следующие $$$m$$$ строк содержат два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), означающих, что команда с номером $$$u$$$ победила команду с номером $$$v$$$. Гарантируется, что каждая неупорядоченная пара команд встретится не более одного раза.
Выведите $$$n$$$ строк, в каждой из них строку, содержащую ровно $$$n$$$ символов. Каждый символ должен быть равен $$$0$$$ или $$$1$$$.
Обозначим за $$$a_{ij}$$$ $$$j$$$-е число в $$$i$$$-й строке. Для всех $$$1 \leq i \leq n$$$ должно быть выполнено $$$a_{ii} = 0$$$. Для всех пар команд $$$i \neq j$$$ число $$$a_{ij}$$$ обозначает результат матча между командой с номером $$$i$$$ и командой с номером $$$j$$$:
Также заметьте, что результаты $$$m$$$ матчей, которые уже были сыграны, не могут быть изменены в вашей лиге.
Красота лиги, представленной в качестве ответа должна быть максимально возможной. Если существует несколько лиг, подходящих под условия и красота которых максимальна, вы можете найти любую из них.
3 1 1 2
010 001 100
4 2 1 2 1 3
0110 0001 0100 1010
Красота лиги в первом тесте равна $$$3$$$, потому что есть ровно три красивые тройки команд: $$$(1, 2, 3)$$$, $$$(2, 3, 1)$$$, $$$(3, 1, 2)$$$.
Красота лиги во втором тесте равна $$$6$$$ потому что существует шесть красивых троек команд: $$$(1, 2, 4)$$$, $$$(2, 4, 1)$$$, $$$(4, 1, 2)$$$, $$$(2, 4, 3)$$$, $$$(4, 3, 2)$$$, $$$(3, 2, 4)$$$.
Название |
---|