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

Чемпионат Урала 2010

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

H. Партия чемпионов Урала

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Перед выборами депутатов Областной Думы в Екатеринбурге обновили все рекламные щиты, стоящие вдоль дорог. Теперь они агитируют за Партию чемпионов Урала. В Екатеринбурге n перекрёстков, некоторые из которых соединены двусторонними дорогами. От любого перекрёстка можно доехать до любого другого. На дороге, соединяющей два перекрёстка, может быть установлено не более одного рекламного щита. Все щиты односторонние, то есть агитация на них видна автомобилистам, едущим только в одном из двух направлений.
Партия чемпионов Урала представила в избирательную комиссию отчёт, содержащий информацию об агитационных материалах. В этом отчёте для каждой пары перекрёстков указано минимальное количество раз, которое автомобилист увидит агитацию при поездке от первого перекрёстка до второго, вне зависимости от выбранного им маршрута.
Председатель областной избирательной комиссии подозревает, что в эту таблицу закралась ошибка, так как ей не удовлетворяет никакая конфигурация дорог и расположение рекламных щитов на них. Проверьте, так ли это.

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

В первой строке записано целое число n (2 ≤ n ≤ 300). В каждой из следующих n строк через пробел записаны n целых чисел. Число в i-й строке на j-й позиции равно минимальному количеству раз, которое автомобилист увидит агитацию при поездке от i-го перекрёстка до j-го. Все числа в таблице лежат в диапазоне от 0 до n − 1. Все числа на главной диагонали равны нулю.

Результат

Если существует конфигурация дорог и щитов, удовлетворяющая приведённой в отчёте таблице, выведите в первой строке «YES». Далее выведите n строк по n символов в каждой. В i-й строке на j-й позиции выведите
  • «0», если i-й и j-й перекрёсток не соединены дорогой;
  • «1», если i-й и j-й перекрёсток соединены дорогой, но на этой дороге нет щита, или на пути от i-го перекрёстка до j-го автомобилист его не увидит;
  • «2», если i-й и j-й перекрёсток соединены дорогой и на пути от i-го до j-го перекрёстка автомобилист увидит щит.
Никакой перекрёсток не должен быть соединён дорогой сам с собой. Если возможных ответов несколько, выведите любой из них.
Если искомой конфигурации дорог и щитов не существует, выведите в единственной строке «NO».

Примеры

исходные данныерезультат
5
0 1 1 1 1
1 0 1 0 1
0 0 0 0 0
2 1 2 0 2
0 0 0 0 0
YES
00202
00210
11001
02000
10100
2
0 1
1 0
NO
Автор задачи: Игорь Чевдарь
Источник задачи: XIV чемпионат Урала по спортивному программированию, 10 апреля 2010 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1770. Партия чемпионов Урала