training_2003_11_17 - условия

Задача A. Новый алхимик ≡

список задач
видимые пробелы
простые формулы
широкий текст

Автор:	XI Всероссийская олимпиада школьников
Входной файл:	input.txt	Ограничение времени:	10 сек
Выходной файл:	output.txt	Ограничение памяти:	200 Мб

Условие

Счастливый день! могу сегодня я
В шестой сундук (сундук еще не полный)
Горсть золота накопленного всыпать.
Немного, кажется, но понемногу
Сокровища растут.
А. С. Пушкин

Алхимик Петя изобрел философский камень, с использованием которого можно проводить некоторое множество алхимических реакций по превращению одних веществ в другие. Масса каждого вещества, вступающего в реакцию, и масса каждого образующегося в результате реакции вещества составляет ровно один грамм. Естественно, закон сохранения массы при этом может нарушаться.

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

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

Формат входного файла

В первой строке записано целое число K — количество различных веществ, участвующих и образующихся в алхимических реакциях. Вторая строка содержит список этих веществ, разделенных пробелом (в списке обязательно есть свинец и золото). Названия веществ не длиннее 10 букв.

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

в первой строке — названия веществ, вступающих в реакцию,
во второй строке — названия веществ, получающихся в результате реакции.

Формат выходного файла

Ваша программа должна вывести в выходной файл либо одно целое число — искомое количество граммов золота, либо сообщение QUANTUM SATIS, если Петя может получить любое количество золота.

Внимание! Вместо 'QUANTUM SATIS' следует выводить число -1.

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

Ограничения

1 ≤ K ≤ 6, 1 ≤ L ≤ 100

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)

1

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`5 ÑÐ²Ð¸Ð½ÐµÑ Ð·Ð¾Ð»Ð¾ÑÐ¾ ÑÐµÑÐ° ÑÑÑÑÑ Ð¼ÐµÐ´Ñ 5 ÑÐ²Ð¸Ð½ÐµÑ Ð·Ð¾Ð»Ð¾ÑÐ¾ ÑÐµÑÐ° ÑÑÑÑÑ ÑÐ²Ð¸Ð½ÐµÑ Ð·Ð¾Ð»Ð¾ÑÐ¾ Ð¼ÐµÐ´Ñ ÑÑÑÑÑ ÑÑÑÑÑ Ð·Ð¾Ð»Ð¾ÑÐ¾ ÑÐµÑÐ° ÑÑÑÑÑ Ð¼ÐµÐ´Ñ ÑÑÑÑÑ ÑÐµÑÐ° Ð·Ð¾Ð»Ð¾ÑÐ¾ ÑÐµÑÐ° ÑÑÑÑÑ Ð·Ð¾Ð»Ð¾ÑÐ¾`	`3`

5
ÑÐ²Ð¸Ð½ÐµÑ Ð·Ð¾Ð»Ð¾ÑÐ¾ ÑÐµÑÐ° ÑÑÑÑÑ Ð¼ÐµÐ´Ñ
5
ÑÐ²Ð¸Ð½ÐµÑ
Ð·Ð¾Ð»Ð¾ÑÐ¾ ÑÐµÑÐ° ÑÑÑÑÑ
ÑÐ²Ð¸Ð½ÐµÑ
Ð·Ð¾Ð»Ð¾ÑÐ¾ Ð¼ÐµÐ´Ñ ÑÑÑÑÑ
ÑÑÑÑÑ Ð·Ð¾Ð»Ð¾ÑÐ¾
ÑÐµÑÐ°
ÑÑÑÑÑ Ð¼ÐµÐ´Ñ
ÑÑÑÑÑ ÑÐµÑÐ° Ð·Ð¾Ð»Ð¾ÑÐ¾
ÑÐµÑÐ° ÑÑÑÑÑ
Ð·Ð¾Ð»Ð¾ÑÐ¾

Задача B. Поезда ≡

список задач
видимые пробелы
простые формулы
широкий текст

Автор:	X Всероссийская олимпиада школьников
Входной файл:	train.in	Ограничение времени:	4 сек
Выходной файл:	train.out	Ограничение памяти:	200 Мб

Условие

В связи с увеличившимся числом аварий на железнодорожной трассе "Нью-Васюки-Петербург" руководство железнодорожной компании решило изменить график движения поездов. Тщательный анализ состояния полотна установил, что оптимальным является следующий график движения: сначала T₁ минут поезд идет со скоростью V₁ метров в минуту, затем T₂ минут со скоростью V₂ м/мин, ..., наконец, T_N минут со скоростью V_N м/мин. В течение интервала T_i (1 ≤ i ≤ N) поезд может стоять.

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

Формат входного файла

В первых двух строках входного файла содержатся натуральные числа, задающие минимально допустимое расстояние L и количество участков пути N. Далее следуют N пар целых чисел T₁, V₁, ..., T_N, V_N, описывающих график движения.

Формат выходного файла

В выходной файл требуется вывести искомый интервал между отправлениями поездов в минутах, не менее чем с тремя верными знаками после десятичной точки.

Ограничения

100 ≤ L ≤ 10000, 1 ≤ N ≤ 1000, 1 ≤ T_i ≤ 1000, 0 ≤ V_i ≤ 1000.

Примеры тестов

№	Входной файл (`train.in`)	Выходной файл (`train.out`)
1	`1000 4 10 0 30 80 15 0 20 100`	`27.5`

Задача C. Числообменник ≡

список задач
видимые пробелы
простые формулы
широкий текст

Автор:	IX Всероссийская олимпиада школьников
Входной файл:	input.txt	Ограничение времени:	5 сек
Выходной файл:	output.txt	Ограничение памяти:	200 Мб

Условие

Числа от 1 до N выписаны подряд в строку. Разрешается менять местами любые два числа, между которыми в строке стоят ровно P1, P2, ... или PM, чисел (числа P1, P2, ..., PM заданы).

Например, пусть N = 5, M = 2, P1 = 3, P2 = 2. Тогда после перестановки чисел в позициях 1 и 4 (между ними стоят 2 числа) и чисел в позициях 1 и 5 (между ними стоят 3 числа) получится по-следовательность 5, 2, 3, 1, 4.

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

Формат входного файла

Файл исходных данных INPUT.TXT содержит (в указанном порядке): N, M, P1, P2, ..., PM. Все числа в файле разделяются пробелами и (или) символами перевода строки. Входные данные корректны.

Формат выходного файла

В выходном файле OUTPUT.TXT должно находиться искомое число.

Частичные решения задачи (количество перестановок < 2 147 483 648) будут оцениваться исходя из 15 баллов. Естественно, в тестирующей системе частичные решения оцениваться не будут.

Ограничения

2 ≤ N ≤ 3000
1 ≤ M ≤ 500
Для всех i (1 ≤ i ≤ M) выполняется 0 ≤ P_i ≤ N - 2

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`5 2 3 2`	`24`