Problem K
Lemonade Trade
Languages
en
ja
The lunch break just started! Your mother gave you one litre of pink lemonade. You do not like pink lemonade and want blue lemonade instead. Fortunately for you the other children in class are willing to trade with you.
Each of them is willing to offer you any quantity of the virtually infinite amount of lemonade they got from their mother, in exchange for their favourite lemonade, according to some exchange rate. The other children are sitting in a long row in the class room and you will walk along the row, passing each child only once. You are not allowed to walk back! Of course, you want to maximise the amount of blue lemonade you end up with. In case you can obtain more than $10$ litres of blue lemonade, this is more than you will need, and you will throw away any excess (and keep the $10$ litres).
Fortunately, you know in advance what everybody is offering for trade. Your task is to write a program to find the maximum amount of blue lemonade that you can obtain.
Input
The input consists of the following:
-
One line containing a single integer $0\leq N \leq 10^5$, the number of children in the class room, excluding yourself;
-
$N$ lines, each containing two strings $O, W$ and a floating point number $0.5 < R < 2$, the name of the lemonade that is offered, the name of the lemonade that is wanted, and the exchange rate: for every litre of lemonade $W$ that you trade you get $R$ litres of lemonade $O$ in return. Exchange rates are given with at most $7$ digits after the decimal point.
All strings are guaranteed to have at most $10$ alphanumeric characters.
Output
Output a single line containing a single floating point number $M$, the maximum amount (in litres) of blue lemonade that you can obtain. In case you could obtain more than $10$ litres, $M$ is considered to be $10$. You are required to output $M$ with absolute precision $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 blue pink 1.0 red pink 1.5 blue red 1.0 |
1.500000000000000 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 blue red 1.0 red pink 1.5 |
0.000000000000000 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 orange pink 1.9 yellow orange 1.9 green yellow 1.9 blue green 1.9 |
10.000000000000000 |
| Sample Input 4 | Sample Output 4 |
|---|---|
8 red pink 1.9 orange red 1.9 yellow orange 1.9 green yellow 1.9 indigo green 0.6 violet indigo 0.6 purple violet 0.6 blue purple 0.6 |
1.688960160000000 |
