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

Открытое личное первенство УрГУ 2007

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

B. Толстые хоббиты

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Ни один хоббит не в состоянии в одиночку противостоять полчищам Мордора… В последний поход против Мордора Гэндальф решил отправить N хоббитов из Шира. Но часть хоббитов наотрез отказалась, жалуясь на то, что другие хоббиты наверняка будут дразнить их толстыми. После опроса всех хоббитов оказалось, что любой хоббит отказывается принять участие в походе в том случае, если с ним в поход выступит хотя бы один хоббит с меньшим весом. К счастью для Средиземья, не все хоббиты знают свой точный вес. В Шире были всего одни весы чашечного типа, позволяющие для пары хоббитов определить, какой хоббит тяжелее. Некоторые пары хоббитов взвешивались на этих весах. Всем хоббитам известен результат всех взвешиваний. Гэндальф абсолютно уверен, что в Шире нет двух хоббитов одного веса. Он заинтересован в том, чтобы отряд состоял из наибольшего количества хоббитов. Однако найти наибольшее множество хоббитов, среди которых ни один не считает себя тяжелей другого, оказалось не так-то просто. Подскажите Гэндальфу, на сколько хоббитов он может рассчитывать. Помните при этом, что хоббиты умные существа и знают, что если Сэм тяжелее Пиппина, а Пиппин тяжелее Фродо, то Сэм и подавно будет тяжелее Фродо.

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

В первой строке дано целое число N — количество хоббитов (2 ≤ N ≤ 100). Все хоббиты пронумерованы целыми числами от 1 до N. В следующих N строках записана матрица размера N × N. Если i-й и j-й хоббит взвешивались на чашечных весах и оказалось, что i-й хоббит тяжелее, то в i-й строке матрицы на j-й позиции стоит единица. Во всех остальных случаях в матрице стоят нули.

Результат

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

Примеры

исходные данныерезультат
2
0 1
0 0
1
2
3
0 0 0
0 0 0
0 0 0
3
1 2 3
Автор задачи: Александр Ипатов
Источник задачи: Восьмое открытое личное первенство УрГУ (3 марта 2007)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1533. Толстые хоббиты