MoneyExchange
SRM 240 · 2005-04-30 · by Jan_Kuipers
SRM 240 · 2005-04-30 · by Jan_Kuipers · Dynamic Programming
Problem Statement
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 aString[] 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.
The exchange rates are described in a
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.
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
8)
{"A 7 A 5","A 1 B 1","B 2 A 2"}
"A"
"A"
Returns: 1.0
type1 can be type2.
Submissions are judged against all 26 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MoneyExchange with a public method double bestRate(vector<string> rates, string type1, string type2) · 26 test cases · 2 s / 256 MB per case