|
Отношения
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 3
111
110
100 | YES
0 1 2
2 1 0 |
| 2 | 3
110
101
011 | NO |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
