Задача C. Цепи зависимости
Задачу добавил: alef
Успешно сдано решений: 6
Кеша Канарейкин решил установить операционную систему L на своем ноутбуке. Однако «обычной установки» ему было явно недостаточно. Ведь требовалось подключать к ноутбуку пару разных принтеров (дома и на работе), сканер, настроить доменную учетную запись. Да еще было бы очень желательно, чтобы можно было просматривать и прослушивать файлы разных форматов...В общем, стало понятно, что потребуется поставить еще целый ряд дополнительных пакетов. Важный момент состоит в том, что некоторые пакеты перед своей установкой требуют наличия в системе других пакетов, и т.д. Кеша хотел бы скачать все пакеты «одной командой», но для этого ему нужен полный список того, что потребуется установить.
У Кеши имеется список пакетов, которые он хотел бы установить. Для каждого пакета из списка Кеши имеется список зависимостей — пакетов, которые должны быть в системе для их установки. Аналогичные списки существуют и для этих вспомогательных пакетов и т.д. Кроме того, есть список пакетов, которые уже установлены в системе.
Ваша задача — определить, сколько пакетов Кеше придется доустановить в систему.
Формат входного файла input.txt
Сначала идут строки с описаниями пакетов и их зависимостей. Каждая строка начинается с имени пакета, а затем идут имена пакетов, от которых он зависит. Если с имени пакета не начинается ни одна строка, считается, что он может быть установлен в систему без предварительной подготовки.
Затем на отдельной строке записано слово Installed
После него на следующих строках через пробел указаны имена пакетов, которые уже установлены в системе (если таковые есть).
Гарантируется, что все данные корректны, в зависимостях нет циклов и что ни один пакет не называется Installed (с буквами в любом регистре). Размер входного файла не превышает 1 Мб
Формат выходного файла output.txt
Первая строка — целое число, количество пакетов, которые должны быть установлены в систему
Пример входного файла
openldap openssl openssl_devel
openldap_clients openssl openssl_devel
openssl lib2xml
openssl_devel gcc gccpp
pam_mount openldap lib_crypto libxml2_devel
lib_crypto openssl_devel
Installed
gcc gccpp
lib_crypto
pam_ldap
Пример выходного файла
7