Украинские Олимпиады
Украинские Олимпиады по Информатике
по Информатике

Материалы

 
 
Донецк'2003, I тур

Алхимия

Известны K видов веществ и N типов алхимических реакций. Каждая реакция по набору входных веществ продуцирует набор выходных. Проведение каждой реакции требует фиксированного времени. Любые вещества, полученные в результате реакций, можно выделять в чистом виде для отдельного использования. Каждого вещества всегда достаточно для любого использования. Вещество, полученное в результате только что закончившейся реакции, можно сразу же использовать в других реакциях. Реакции могут проходить одновременно.

Задание

Напишите программу ALCHEMY, которая по информации об известных веществах и реакциях определяет за какое наименьшее время можно получить целевое вещество.

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

Первая строка входного файла ALCHEMY.DAT содержит четыре целых числа: K (3£K£250) — количество веществ, N (3£N£500) — количество реакций, M (1£M<K) — количество имеющихся сначала веществ, а также номер целевого вещества.

Далее следуют N блоков, которые описывают реакции. Каждый блок состоит из трех строк: первая содержит натуральное число — время, необходимое для проведения реакции, вторая строка — количество веществ, которые вступают в реакцию, и перечень этих веществ, третья строка — количество веществ, которые образовываются в результате реакции, и их перечень.

Вещества, имеющиеся сначала, имеют номера от 1 до M, а все остальные — от M+1 до K. Сумма времен проведения всех реакций не превышает 2*109.

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

Единственная строка выходного файла ALCHEMY.SOL должна содержать целое число — найденное минимальное время, за которое может быть получено целевое вещество.

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

Для приведенного примера входных данных, целевое вещество 4 можно получить, если на протяжении первых трех единиц времени провести реакцию 2, а после этого на протяжении двух единиц времени провести реакцию 3. Таким образом, за 5 единиц времени будет получено требуемое вещество.

Пример входных данных
4 3 1 4
8
1 1
1 4
3
1 1
2 2 3
2
2 1 3
1 4
Пример выходных данных
5

 

Олимпиады

Всеукраинские
1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004

Отборочные сборы
1992 1993 1994 1996 1997 1998 1999 2000 2001 2002 2003 2004

Международные
1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004

Всесоюзные
1988 1989 1990 1991 1992

© Разработано рабочей группой UOI 1998-2004 гг.