Hide

Problem E
レモネードの交換

Languages en ja
/problems/lemonadetrade/file/statement/ja/img-0001.jpg
Picture by David Wargert via Flickr.

昼休みが始まった!お母さんから$1$リットルのピンクレモネードを渡されているけど、あなたはピンクレモネードが好きではなく、あなたが好きなのはブルーレモネードだ。

幸い、クラスの他の生徒が交換したがっている。彼らは、それぞれの母親から無限の量のレモネードをもらっているので、彼らの好きなレモネードを交換レートに従って好きなだけ交換することができる。生徒は教室内に一列に座っており、あなたは列に沿ってそれぞれの生徒と$1$回ずつしか交換することができない。すなわち、列を戻ることはできない! もちろん、あなたは最終的にできるだけ多くのブルーレモネードを手に入れたいが、あなたが欲しいのは$10$リットルだけなので、それより多くのブルーレモネードを手に入れた場合、余りは捨ててしまう(そして、$10$リットルだけ保持する)。

幸い、各生徒の提示する交換レートは事前に知ることができる。あなたのタスクは、できるだけ多くのブルーレモネードを手に入れることだ。

入力

入力は以下の内容を含む。

  • 先頭行は $0\leq N \leq 10^5$の整数で、クラスのあなた以外の生徒数を表す。

  • それ以降の $N$ 行は $O, W$$2$ つの文字列と $0.5 < R < 2$ の浮動小数点数で、提供するレモネードの名前、要求するレモネードの名前、交換レートを表す。すなわち、レモネード $W$$1$リットル提供するごとに、レモネード $O$$R$ リットル受け取る。交換レートは小数点以下最大$7$桁で与えられる。

文字列は最大$10$文字のアルファベットで与えられる。

出力

出力は単一行で、単一の浮動小数点数 $M$を含む。これは、ブルーレモネードを手に入れられる最大量(リットル単位)を示す。$10$ リットルより多く手に入れられる場合には、$M$$10$. になる。$M$ の精度は $10^{-6}$ の桁まで含める必要がある。

サンプル入力 1 サンプル出力 1
3
blue pink 1.0
red pink 1.5
blue red 1.0
1.500000000000000
サンプル入力 2 サンプル出力 2
2
blue red 1.0
red pink 1.5
0.000000000000000
サンプル入力 3 サンプル出力 3
4
orange pink 1.9
yellow orange 1.9
green yellow 1.9
blue green 1.9
10.000000000000000
サンプル入力 4 サンプル出力 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