Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Алхимия

Как известно, алхимия как наука возникла в средневековье. В те времена данная наука очень немногими чертами была подобна современной химии. Но оставила заметный след в истории и многие химики об этом периоде отзываются с теплотой.

Недавно, были найдены древние книги по алхимии, в которых, возможно, описаны реакции, которые могут привести к получению новых элементов.

Исследователи этих книг описали все богатство информации в виде m реакций, в результате которых происходит превращение одного вещества в другое.

В связи с данным открытием исследователей интересует, можно ли с помощью описания найденных m реакций получить из одного вещества другое, и если это возможно, то какое минимальное количество реакций надо использовать?

Входные данные:
Первая строка файла input.txt содержит число m (0 ≤ m ≤ 1000) – количество реакций, найденных в книгах.

Далее следует m строк вида вещество1 -> вещество2, где вещество1 – название исходного вещества, вещество2 – название продукта алхимической реакции. Вещества разделяются при помощи ровно 4 символов (пробел, минус(-), знак больше(>) и еще один пробел).

Далее следует 2 строки: m+2-я строка содержит название вещества из которого необходимо получить вещество, название которого располагается на строке m+3.

Во входном файле упоминается не более 100 различных веществ. Название каждого из веществ состоит из строчных и прописных латинских букв и имеет длину не более 20 символов. Строчные и прописные буквы различаются, т.е. вещества Aurum и aurum – разные.

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

Если невозможно получить из исходного вещества конечное, то необходимо вывести -1.


Примеры:
input.txt output.txt
1 5
Aqua -> AquaVita
AquaVita -> PhilosopherStone
AquaVita -> Argentum
Argentum -> Aurum
AquaVita -> Aurum
Aqua
Aurum
2
2 5
Aqua -> AquaVita
AquaVita -> PhilosopherStone
AquaVita -> Argentum
Argentum -> Aurum
AquaVita -> Aurum
Aqua
Osmium
-1

Сложность задачи: 15%



Проверку могут осуществлять только зарегистрированные пользователи!


Показать обсуждение


На сайте гостей 16, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]