usaco-2.3.5 控制公司
题目描述
有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分.例如,福特公司拥有马自达公司 12%的股票.据说,如果至少满足了以下条件之一,公司 A 就可以控制公司 B 了:
- 公司 A = 公司 B.
- 公司 A 拥有大于 50%的公司 B 的股票.
- 公司 A 控制 K(K >= 1)个公司,记为 C1, ..., CK,每个公司 Ci 拥有 xi%的公司 B 的股票,并且 x1+ .... + xK > 50%.
你将被给予一系列的三对数（i,j,p）,表明公司 i 享有公司 j 的 p%的股票.计算所有的数对（h,s）, 表明公司 h 控制公司 s.至多有 100 个公司.
写一个程序读入三对数（i,j,p）,i,j 和 p 是都在范围(1..100)的正整数,并且找出所有的数对（h,s）,使得公司 h 控制公司 s.
INPUT FORMAT
- 第一行: N,表明接下来三对数的数量.
- 第二行到第 N+1 行: 每行三个整数作为一个三对数（i,j,p）,如上文所述.
SAMPLE INPUT
3
1 2 80
2 3 80
3 1 20
OUTPUT FORMAT
输出零个或更多个的控制其他公司的公司.每行包括两个整数表明序号为第一个整数的公司控制了序号为第二个整数的公司.将输出的每行以第一个数字升序排列（并且第二个数字也升序排列来避免并列）.请不要输出控制自己的公司.
SAMPLE OUTPUT (file concom.out)
1 2
1 3
2 3