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

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

HotLog


 

Игуана

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

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

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

Однако и эта задача оказалось непростой, так как клеток может не хватить для привезенных животных. А в одну клетку можно поместить только совместимых животных. Зоологи составили таблицу совместимости животных, представив ее в виде матрицы A={aij} размером N×N. Если животные с номерами i и j совместимы, то aij=0, а если - нет, то aij=1. Необходимо определить минимальное количество клеток для безопасного размещения животных, когда во всех клетках находятся только совместимые между собой животные. При этом в клетке может находиться одно, два и более животных.

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

Первая строка входного файла INPUT.TXT содержит число N - количество животных (1 ≤ N ≤ 18). Далее идет N строк по N чисел в каждой – матрица совместимости животных.

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

В выходной файл OUTPUT.TXT выведите одно целое число – минимальное количество клеток, необходимое для безопасного размещения животных.

Примеры

INPUT.TXTOUTPUT.TXT
15
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
5
21
0
1

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru