C - 変わった単位

Contest Duration: 2013-10-05(Sat) 12:00 - 2013-10-05(Sat) 13:30 (local time) (90 minutes) Back to Home

C - 変わった単位 Editorial

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

多くの単位は $10$ とその累乗数を元に作られています。ですが、この世の単位にはそうでないものがあります。
有名なものとしては時間に関する単位です。 $1$ 分は $60$ 秒、 $1$ 時間は $60$ 分、 $1$ 日は $24$ 時間、などです。

いま、あなたに単位の換算表が与えられます。この換算表を元に、「最も大きい単位」を「最も小さい単位」で表したとき、
どのように表せるかを出力するプログラムを書いてください。例えば、

$1week$ $=$ $7day$
$1day$ $=$ $24hour$
$1hour$ $=$ $60min$
$1min$ $=$ $60sec$

と換算表が与えられたとき、 $1week$ $=$ $604800sec$ と出力してください。

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $large_1$   $m_1$   $small_1$ 
 $large_2$   $m_2$   $small_2$ 
:
 $large_{N}$   $m_N$   $small_{N}$

$1$ 行目は、換算表の行数を表す整数 $N\ (1≦N≦200)$ が $1$ 行で与えられる。
$2$ 行目から、 $N+1$ 行目までの $N$ 行で、換算表が与えられる。

$i\ (1≦i≦N)$ 行目において、単位 $large_i$ 、係数 $m_i$ 、単位 $small_i$ が半角空白区切りで与えられる。
$i\ (1≦i≦N)$ 行目において、 $1*large_i$ $=$ $m_i*small_i$ が成立する。
単位名 $large_i$ と $small_i$ はいずれも $10$ 文字以下の半角英小文字から構成される。

$1$ 番大きい単位を $1$ 番小さい単位で表したとき、係数 $M$ は $10^9$ を超えない整数である。
換算表に記載される単位は、必ず別の大きさを持つことが保証されている。つまり、同じ大きさで別名の単位は存在しない。
換算表に記載される単位から、必ず最大・最小の単位を特定できることが保証されている。
換算表に記載される単位は順不同であり、必ずしも大きな単位から順に記載されているとは限らない。

また、 $i$ 行目の入力が隣接する単位との関係を示すとは限らない。
例えば、hour > min > sec という順序関係があるとき、 hour 3600 sec といった入力もありうる。
ただし、換算表には矛盾するような記載はない。

出力

最大の単位を $a$ 、最小の単位を $b$ としたとき、係数 $M$ を用いて $1a$ $=$ $Mb$ の形式で出力せよ。
なお、出力の最後には改行をいれること。

入力例 1

Copy

4
week 7 day
day 24 hour
hour 60 min
min 60 sec

4
week 7 day
day 24 hour
hour 60 min
min 60 sec

出力例 1

Copy

1week=604800sec

1week=604800sec

$1week$ $=$ $7*24*60*60sec$ $=$ $604800sec$

入力例 2

Copy

3
sic 29 cou
gal 493 cou
gal 17 sic

3
sic 29 cou
gal 493 cou
gal 17 sic

出力例 2

Copy

1gal=493cou

1gal=493cou

$1gal$ $=$ $17*29cou$ $=$ $493cou$
$2$ 行目に、 $1gal$ $=$ $493cou$ が与えられていて、実は演算の必要がないです。
$2$ 行目は、入力セクションの $6$ で記述したように、隣接する単位との関係を示したものではありません。

入力例 3

Copy

5
chou 360 shaku
jou 100 sun
ken 60 sun
li 2160 ken
li 12960 shaku

5
chou 360 shaku
jou 100 sun
ken 60 sun
li 2160 ken
li 12960 shaku

出力例 3

Copy

1li=129600sun

1li=129600sun

$1li$ $=$ $2160*60sun$ $=$ $129600sun$
$1$ 行目、 $2$ 行目、 $5$ 行目のように、演算に不要な入力が与えられることもあります。