Покажи мне деньги
Фрэнк Маркс работает в финансовом отделе крупной компании. У его компании клиенты по всему миру, и она должна иметь дело с множеством различных валют. Сотрудники часто приходят в финансовый отдел с запросами на определенные суммы денег, такие как 100 американских долларов или 452 евро. Если у Фрэнка есть наличные, он выдает сотруднику именно то, что ему нужно; если у него недостаточно запрашиваемой валюты, он заменяет ее другой. Это иногда бывает сложно, потому что у него может быть много различных валют на выбор, и он хотел бы выбрать ту, которая позволяет ему максимально приблизиться к первоначальной заявке, не снижая сумму (он должен предоставить как минимум запрашиваемую стоимость). Например, предположим, что у Фрэнка есть шесть различных валют - A, B, C, D, E и F - и он знает следующие обменные курсы:
23 A = 17 B
16 C = 29 E
5 B = 14 E
1 D = 7 F
Если поступает заявка на 100 A, но у Фрэнка меньше 100 A в наличии, он может заменить их на 74 B (эквивалентно примерно 100.12 A), 115 C (эквивалентно примерно 100.72 A) или 207 E (эквивалентно примерно 100.02 A). Таким образом, лучшая доступная замена для него - это 207 E. Обратите внимание, что у Фрэнка недостаточно информации, чтобы найти связь между валютами A и D или валютами A и F. Также у Фрэнка в наличии не более 100000 единиц любой одной валюты, поэтому он не смог бы удовлетворить запрос на 64000 A с использованием валюты E и должен был бы использовать 73078 C вместо этого.
Определение идеальной замены валюты, которую следует использовать, когда у него полностью закончилась запрашиваемая валюта, занимает много времени, поэтому Фрэнк хотел бы, чтобы программа выполняла расчеты за него.
Входные данные
Каждый тестовый случай начинается с положительного целого числа n, указывающего количество обменных курсов. Следующие n строк будут иметь вид
val_1 name_1 = val_2 name_2
где name_1 и name_2 - это названия двух различных валют, а val_1 и val_2 - положительные целые числа ≤ 30, указывающие соотношение между двумя валютами. Не будет более 8 различных названий валют, и любые две валюты будут объединены вместе не более одного раза. Названия валют будут состоять из не более десяти буквенных символов. Входные данные не будут содержать противоречий (таких как 1A = 2B, 1B = 2C и 1C = 2A). После этих n строк будет одна строка вида
val name
которая указывает сумму (положительное целое число, не превышающее 100000) и название запрашиваемой валюты. Строка, содержащая 0, будет следовать за последним тестовым случаем.
Выходные данные
Для каждого тестового случая напечатайте номер случая и ближайшую замену, не снижая запрашиваемую стоимость, предполагая, что у Фрэнка нет запрашиваемой валюты, но он полностью обеспечен всеми другими валютами. Для каждой задачи будет уникальный ответ.