Programming Problem #16
"Company Control"

It is not uncommon for one company to become a partial owner of another company by acquiring some percentage of its stock. For example, to say that 'Amalgamated owns 35% of CashCow' means that Amalgamated has acquired 35% of CashCow's stock. The percentage of company B's stock that is held by company A is called the controlling interest of A in B and is written c(A,B). For example, c(Amalgamated,CashCow)=0.35. Company A is said to control company B provided that at least one of the following is true:
  1. A=B; (every company controls itself),
  2. c(A,B) > 0.50; (i.e., A owns more than 50% of B), or
  3. A controls companies C1,...,Ck such that c(C1,B)+...+c(Ck,B) > 0.50.
Note that condition 2 is just a special case of condition 3. Given a set of companies together with their controlling interests, your job is to determine those companies that are controlled by another company.

The input consists of one or more company sets that are separated by a single blank line. A company set consists of one or more lines of the form 'A B i', where A and B are uppercase letters denoting companies and i=c(A,B). For each company set, display all pairs of distinct companies (A,B) such that A controls B, using the format shown in the examples below.

Input must be read from the file "prob16.in", and output must be written to the file "prob16.out". All output to the screen will be ignored.

Example Input

<BOF>
B C 25
A D 36
D E 63
B A 48
C D 30
D B 52
E C 30

F P 30
P Q 52
Q X 51
X Z 70
Z X 20
X Q 20
<EOF>

Example Output

company D controls company B
company D controls company C
company D controls company E
 
company P controls company Q
company P controls company X
company P controls company Z
company Q controls company X
company Q controls company Z
company X controls company Z
Dr. Eric Shade