Игуана
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 5
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 |
| 2 | 1
0 | 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
