Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Отношения

(Время: 1 сек. Память: 16 Мб Сложность: 54%)

Бинарным отношением R на множестве X называется множество упорядоченных пар элементов из X. Если X конечно и содержит n элементов, то отношение можно задать как квадратную булеву матрицу размера n×n.

В некоторых случаях бывает важно задать отношение в более компактной форме. Один из способов компактного задания отношений применяется, в частности, при описании грамматик операторного предшествования.

Рассмотрим две функции f и g, каждая из которых сопоставляет элементам X целые числа. Будем говорить, что эти функции описывают отношение R, если для любых x и y из X пара (x, y) принадлежит R тогда и только тогда, когда f(x) ≤ g(y).

По заданному отношению R, найдите способ описать его указанным образом с помощью двух функций f и g, либо выясните, что это невозможно сделать.

Входные данные

Первая строка входного файла INPUT.TXT содержит n - количество элементов в множестве X = {x1, x2, …, xn} (1 ≤ n ≤ 1 000). Следующие n строк описывают отношение R. Каждая строка содержит n символов, j-й символ i-й из этих строк равен 1, если (xi, xj) принадлежит R, и 0 в противном случае.

Выходные данные

На первой строке выходного файла OUTPUT.TXT выведите "YES", если отношение можно описать указанным образом. В этом случае вторая строка должна содержать n целых чисел в диапазоне от -109 до 109 - значения функции f на элементах x1, x2, … , xn, соответственно, а третья строка должна описывать функцию g аналогичным образом. Если отношение нельзя закодировать описанным образом с помощью двух функций, выведите "NO" на первой строке выходного файла.

Примеры

INPUT.TXTOUTPUT.TXT
13
111
110
100
YES
0 1 2
2 1 0
23
110
101
011
NO

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483