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

Ural SU contest. Petrozavodsk training camp. Summer 2008

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

G. Смертельная битва

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вступление

Чтобы монстры из Внешнего мира смогли завоевать Землю, они должны одержать десять побед подряд в Смертельной Битве. Турниры проводятся раз в поколение, и бойцы Земли потерпели уже девять поражений. Настал час решающей Смертельной Битвы.

Задача

В Смертельной Битве участвуют N монстров и M лучших бойцов Земли. По правилам турнира, каждый монстр должен драться с одним из людей (все монстры с разными людьми). В случае если хотя бы один монстр одержит победу, то Земля навеки перейдёт во владение ужасного императора Внешнего мира. Впрочем, за людьми остаётся право выбора соперников и очерёдности боёв.
Бог Рейден, покровитель Земли, должен выбрать бойцов так, чтобы все люди одержали победу над соперниками. Для каждого из бойцов Земли известно, каких монстров он способен победить. Для начала, требуется выбрать пару соперников на первый бой.
Так, Лю Кэн хочет драться с Горо, но он единственный боец, способный победить Шан Цунга, в то время как Горо может быть повержен и другими бойцами, например, Джонни Кейджем. Поэтому первый бой между Лю Кэном и Горо даже в случае победы Лю Кэна неизбежно приведёт к захвату Земли, так как затем Шан Цунг одержит победу над своим соперником.
Определите, какие пары ни в коем случае не должны быть выбраны Рейденом, чтобы у людей остался шанс сохранить свою свободу.

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

В первой строке даны целые числа N и M. 1 ≤ N ≤ 300; NM ≤ 1500. Далее приведена матрица A из нулей и единиц размера N × M. Aij = 1, если и только если j-й боец Земли способен одержать победу над i-м монстром.

Результат

Выведите матрицу B размера N × M. Bij должно равняться единице, если на первый бой не может быть выбрана пара соперников (i, j), и нулю в противном случае.

Примеры

исходные данныерезультат
4 4
1111
1000
1111
1111
1000
0111
1000
1000
4 5
10000
10000
10000
10000
11111
11111
11111
11111
Автор задачи: Магаз Асанов (подготовка — Александр Ипатов)
Источник задачи: Ural SU Contest. Petrozavodsk Summer Session, August 2008
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1676. Смертельная битва