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

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

HotLog


 

Взрывчатка

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

На территории базы противника расположены N арсеналов, которые нужно уничтожить. Вы, Агент-070, имеете запас взрывчатки, достаточный для того, чтобы взорвать все N арсеналов по одному. Но при этом велик риск обнаружения.

Однако Вам известно, что при взрыве каждого арсенала создаётся взрывная волна, которая может достичь других арсеналов и спровоцировать их взрыв. Эти арсеналы тоже будут создавать свои взрывные волны. В Центре вам выдали таблицу, в которой для каждого арсенала указано, какие другие арсеналы попадут под его взрывную волну.

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

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

В первой строке входного файла INPUT.TXT содержится число N – количество арсеналов на территории базы (1 ≤ N ≤ 100).

Далее дана таблица отношений: в N строках содержится по N символов, j-ый символ i-ой строки равен «1», если при взрыве i-го арсенала j-ый попадёт под его взрывную волну и «0» иначе.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
13
000
100
100
2
23
010
001
000
1

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая личная олимпиада
 Вторая личная олимпиада
 Третья личная олимпиада
 Четвертая личная олимпиада
 Пятая личная олимпиада
 Шестая личная олимпиада
 Седьмая личная олимпиада
 A. Три поросёнка
 B. Слоны на шахматной доске
 C. Взрывчатка
 D. Химические реакции

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