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

Соревнование школьников. Октябрь 2002

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

E. Тараканы!

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Хорошо известно, что самым живучим биологическим видом на Земле являются тараканы. Они живут всюду, где можно найти еду. А поскольку в еде они неприхотливы, то живут они просто везде.
Маленький Леша учится в школе на космической станции. Во время одного из школьных состязаний его класс вышел в финал. Задание финального конкурса заключается в том, чтобы как можно быстрее выморить всех тараканов в грузовом модуле.
За долгую историю проведения состязаний у школьных команд выработалась единая тактика в этом конкурсе. Тактика такова: в один из отсеков модуля запускается ядовитый газ, после этого открывается одна перегородка, соединяющая этот отсек с одним из соседних. Тараканы, не выдерживая запаха газа, перебегают в соседнее помещение. После того, как в обработанном отсеке не останется ни одного таракана, перегородка закрывается. Далее аналогичным образом обрабатывается другой отсек и т.д. Главная цель — загнать всех тараканов в шлюзовой отсек грузового модуля. Тогда открывается внешняя дверь и, со свистом и визгом, тараканов засасывает в открытый космос.
В своём классе Леша как раз отвечает за программирование пульта управления перегородками. Перегородки открываются довольно медленно, поэтому для победы в конкурсе важно обойтись минимально возможным количеством подъемов перегородок. Ваша задача состоит в том, чтобы помочь Леше подсчитать такое минимальное количество.

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

В первой строке записано название шлюзового отсека. Каждая следующая строка содержит описание одной из перегородок — название двух отсеков, разделенных дефисом. Последняя строка содержит всего один символ: "#". Тараканы живут во всех отсеках грузового модуля. Из любого отсека можно пройти в шлюзовой отсек, пройдя через несколько перегородок. Общее количество отсеков не превышает 30. Название отсека состоит не более чем из 20 латинских букв и цифр, большие и маленькие буквы следует различать. В начальный момент времени все перегородки закрыты.

Результат

Выведите минимальное количество перегородок, которые надо открыть (а потом закрыть), чтобы перегнать всех тараканов в шлюзовый отсек.

Пример

исходные данныерезультат
Gateway
Machinery-Gateway
Machinery-Control
Control-Central
Control-Engine
Central-Engine
Storage-Gateway
Storage-Waste
Central-Waste
#
6
Автор задачи: Евгений Крохалев
Источник задачи: USU Open Collegiate Programming Contest October'2002 Junior Session
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1213. Тараканы!