Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
206. Алхимик
Генерация всех подмножеств, сочетаний, перестановокДругие задачи на графы
Олимпиадные задачи на русском языке
| 02/07/2007 | Лето 2007 дорешивание ( 2F) |
| 04/07/2007 | Лето 2007 - 2 (F) |
Ограничения: время – 1s/2s, память – 2MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Алхимик Петя изобрел философский камень, с использованием которого можно проводить некоторое множество алхимических реакций по превращению одних веществ в другие. Масса каждого вещества, вступающего в реакцию, и масса каждого образующегося в результате реакции вещества составляет ровно один грамм. Естественно, закон сохранения массы при этом может нарушаться.
Изначально у Пети имеется один грамм свинца. С помощью философского камня Петя может превратить свой свинец в другие вещества, на которые он потом также сможет воздействовать философским камнем. Выполняя одну за другой алхимические реакции, Петя стремится получить как можно больше золота.
Требуется написать программу, определяющую по заданному описанию алхимических реакций, выполняемых философским камнем, наибольшее количество золота, которое может получить Петя.
Для ввода используется кодировка 866 (DOS). В первой строке ввода записано целое число `K\ (1\ ≤\ K\ ≤\ 6)` – количество различных веществ, участвующих и образующихся в алхимических реакциях.
Вторая строка содержит список этих веществ, разделенных пробелом (в списке обязательно есть свинец и золото). Названия веществ не длиннее 10 букв.
В третьей строке записано целое число `L\ (1\ ≤\ L\ ≤\ 100)` – количество типов реакций, выполняемых философским камнем.
Далее в файле идут `L` описаний этих реакций. Каждое описание реакции состоит из двух строк:
- в первой строке – названия веществ, вступающих в реакцию,
- во второй строке – названия веществ, получающихся в результате реакции.
Ваша программа должна вывести либо одно целое число – искомое количество граммов золота, либо –1, если Петя может получить любое количество золота.
Ниже приведены примеры входного и выходного файлов для представленных на рисунке алхимических реакций, выполняемых философским камнем.
Пример ввода
5 свинец золото сера ртуть медь 5 свинец золото сера ртуть свинец золото медь ртуть ртуть золото сера ртуть медь ртуть сера золото сера ртуть золото
Пример вывода
3
