2013年9月18日 星期三

388 - Galactic Import

隨著新系統的引進,星系之間的出口進口貿易變得更加容易,HyperCommodities 打算進口物品從不同的星系,每個星系中的行星的原物料都有不同的價值。

  • 每個星系中最多有 26 個星球,每個星球編號從 'A' 到 'Z'。
  • 每個星球都可以進口和出口,而且都有不同的原物料。
  • 其中會存在兩個星球間有貿易路線,每當原物料由其他星球轉口出去,每轉一次原物料價值將會折損當下的 5%。
  • 至少存在一個星球會向地球開放貿易。
找到其中一個星球的原物料進口到地球具有最高價值。

Input

輸入有多組測資。

每組測資第一行會有一個整數 N 表示描述星球間的關係。

每一行的格式如下:
  1. 星球的英文字母代號
  2. 空白
  3. 原物料的價值 d.dd
  4. 空白
  5. 一組字串,表示可以出口到的地方。以 '*' 表示地球。

Output

對於每組測資,輸出 ``Import from P'',P 為最高價值的星球代號。如果有多個,則選擇字典順序最小的。

Sample Input

1
F 0.81 *
5
E 0.01 *A
D 0.01 A*
C 0.01 *A
A 1.00 EDCB
B 0.01 A*
10
S 2.23 Q*
A 9.76 C
K 5.88 MI
E 7.54 GC
M 5.01 OK
G 7.43 IE
I 6.09 KG
C 8.42 EA
O 4.55 QM
Q 3.21 SO

Sample Output

Import from F
Import from A
Import from A