ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат УрГУ 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

F. Лживый футбол

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Напомним, что в турнире по настольному футболу среди программистов в городе Петрозаводске принимали участие N команд. В ходе турнира каждая сыграла с каждой ровно один раз. За победу команда получала 3 очка, за ничью 1 очко, за поражение 0 очков. После окончания турнира капитан каждой команды высказался: «мы набрали очки в игре с командой X» или «мы не набрали очков в игре с командой X». Каждый капитан мог сделать несколько высказываний, но не обязательно он высказался о каждом сопернике. Организаторы сборов в Петрозаводске поняли, что некоторые капитаны всегда врут, зато все остальные всегда говорят правду.
Разве вы ещё не знаете, какая команда стала победителем? Если нет, то попробуйте по имеющейся информации найти любой возможный результат турнира, если такой существует.

Исходные данные

В первой строке ввода дано целое число 1 ≤ N ≤ 100. В следующих N строках по N чисел в строке приведена матрица высказываний A из чисел 0, 1 и –1. Aij = 1 означает, что, по словам капитана i-й команды, его команда набрала очки в игре против j-й команды. Aij = 0 означает, что i-я команда не набрала очков в игре против j-й команды (опять же, по словам капитана i-й команды). Aij = –1 означает, что капитан i-й команды воздержался от высказываний по поводу встречи с j-й командой. Гарантируется, что для любого i Aii = –1.

Результат

Если какое-то решение существует, выведите матрицу B размера N × N. Bij должно равняться количеству очков, которое получила i-я команда в игре против j-й команды. Если решения нет, выведите «Impossible».

Примеры

исходные данныерезультат
3
-1 1 0
1 -1 -1
0 1 -1
0 0 1
3 0 3
1 0 0
5
-1 1 1 0 0
0 -1 1 -1 -1
1 0 -1 -1 -1
0 -1 -1 -1 1
1 -1 -1 0 -1
Impossible
Автор задачи: Сергей Пупырев
Источник задачи: XI Чемпионат УрГУ по программированию, 7 октября, 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1485. Лживый футбол