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

Ural SU contest. Petrozavodsk training camp. Winter 2009

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

F. Работа для роботов

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
На планете PTZZZ живёт и работает n роботов. С незапамятных времён некоторые роботы дружат между собой, а некоторые — нет.
Ровно один раз в день некоторые роботы выходят на работу, а все остальные идут в парк развлечений и отдыхают. При этом на работу должен выйти хотя бы один робот. Определением того, кто будет работать, а кто отдыхать, занимается робот-директор. Работа настолько важна для роботов, что первый день, когда робот-директор принял решение, был назван Первым днём Мира.
Если окажется так, что в некоторый день на работу вышли в точности те же роботы, что и в какой-нибудь из предыдущих дней, то робот-директор заржавеет от горя. Кроме того, закон не позволяет роботу-директору отправлять на работу группу роботов, в которой какие-нибудь два робота не будут дружить между собой.
Робот-директор не хочет ржаветь от горя как можно дольше, поэтому он старается каждый раз отправлять на работу другую группу роботов. Однако, как легко понять, различных групп роботов всё же конечное число, поэтому роботу-директору в конце концов придётся заржаветь. От Вас требуется найти лишь номер дня, в который это произойдёт.

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

В первой строке записано целое число n, количество роботов на PTZZZ (1 ≤ n ≤ 50). В каждой из следующих n строк записано по n цифр 0 или 1. j-я цифра в i-й строке равна единице, если i-й и j-й роботы дружат между собой, и нулю в противном случае. Гарантируется, что i-я цифра в i-й строке равна нулю, а j-я цифра в i-й строке совпадает с i-й цифрой в j-й строке.

Результат

Выведите номер дня, в который робот-директор вынужден будет заржаветь от горя.

Пример

исходные данныерезультат
6
011100
101100
110100
111000
000001
000010
19
Автор задачи: Михаил Колодяжный (подготовка — Алексей Самсонов)
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, February 2009
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1695. Работа для роботов