1995 ACM Mid-Central Programming Contest
Problem D - Galactic Import

Source File: D.{c|cpp|pas}
Input File: D.in
Output File: D.out

With the introduction of the new ThrustoZoom gigadimensional drive, it has become possible for HyperCommodities, the import/export conglomerate from New Jersey, to begin trading with even the most remote galaxies in the universe. HyperCommodities wants to import goods from some of the galaxies in the Plural Z sector. Planets within these galaxies export valuable products and raw materials like vacuuseal, transparent aluminum, digraphite, and quantum steel. Preliminary reports have revealed the following facts:

HyperCommodities has assigned a relative value (a positive real number less than 10) to each planet's chief export. The higher the number, the more valuable the product. More valuable products can be resold with a higher profit margin in domestic markets. The problem is to determine which planet has the most valuable export when shipping fees are taken into account.

The input consists of one or more galaxy descriptions. Each galaxy description begins with a line containing an integer N which specifies the number of planets in the galaxy. The next N lines contain descriptions of each planet, which consist of:

  1. The letter used to represent the planet.

  2. A space.

  3. The relative value of the planet's export, in the form d.dd.

  4. A space.

  5. A string containing letters and/or the character `*'; a letter indicates a shipping line to that planet, and a `*' indicates a willingness to open a ThrustoZoom shipping line to Earth.

For each galaxy description, output a single line which reads "Import from P" where P is the letter of the planet with the most valuable export, once shipping fees have been taken into account. (If more than one planet have the same most valuable export value then output the plant which is alphabetically first).

A sample input file is shown here:

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
The following output file should be produced from the above sample input:
Import from F
Import from A
Import from A