TopCoder problem "MoneyExchange" used in SRM 240 (Division II Level Three)



Problem Statement

    You have money of type1 and want to exchange it for money of type2. You are at an obscure money exchange office that offers you a number of exchange rates. The office doesn't have exchange rates for every type to every other type, but you can change multiple times (for example, first change type A for type B and then type B for type C). There may be multiple ways to change certain types for others and different ways may have different (combined) exchange rates. The exchange office is not stupid and it is impossible to make infinite amounts of type2 by continuously exchanging.



The exchange rates are described in a String[] rates. Every element of rates is formatted is follows: "type1 num1 type2 num2", with type1 and type2 consisting of only uppercase letters and num1 and num2 of only digits. Such an element in rates means that you can exchange num1 units of type1 for num2 units of type2. You are allowed to exchange fractional units.



What is the maximal amount of type2 you can obtain by exchanging one unit of type1? Return this amount as a double. If it is impossible to obtain type2 return -1.
 

Definition

    
Class:MoneyExchange
Method:bestRate
Parameters:String[], String, String
Returns:double
Method signature:double bestRate(String[] rates, String type1, String type2)
(be sure your method is public)
    
 

Notes

-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-type1 and type2 each have length between 1 and 50, inclusive.
-Every character in type1 and type2 is an uppercase letter.
-rates contains between 0 and 50 elements, inclusive.
-Each element of rates has length between 1 and 50, inclusive.
-Each element of rates is formatted as described in the statement.
-The values represented by num1 and num2 in each element of rates are between 1 and 10, inclusive.
-rates is such that you can't make infinite amounts of type2
 

Examples

0)
    
{"EUR 8 USD 10", "USD 10 EUR 7"}
"EUR"
"USD"
Returns: 1.25
For 1 euro you can obtain 1.25 dollars.
1)
    
{"EUR 0008 USD 0010"}
"USD"
"EUR"
Returns: -1.0
This exchange office doesn't accept dollars. Beware of leading zeroes.
2)
    
{"EUR 8 USD 10","EUR 1 GOODBUY 2","GOODBUY 1 USD 2"}
"EUR"
"USD"
Returns: 4.0
Instead of directly buying dollars, you'd better buy type "GOODBUY" first.
3)
    
{"A 1 B 2","A 1 C 3","B 2 D 3","C 9 D 10","D 7 E 2"}
"A"
"E"
Returns: 0.9523809523809523
4)
    
{}
"TYPEA"
"TYPEB"
Returns: -1.0
5)
    
{"A 7 A 5","A 1 B 1","B 2 A 2"}
"A"
"A"
Returns: 1.0
type1 can be type2.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3529

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6539&pm=3529

Writer:

Jan_Kuipers

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming