#P18581. Money Laundering
Money Laundering
Money Laundering
一家公司 A 今年获得了 100 欧元利润。Ivan 持有它 52.8% 的股份,Robi 持有 47.2%,因此二人分别获得 52.8 和 47.2 欧元。
为了让直接持股关系不再这么明显,他们成立了空壳公司 B,并调整持股结构:Ivan、Robi、B 和 A 自己分别持有 A 的 1%、2%、49% 和 48%;B 自己、A、Ivan 和 Robi 分别持有 B 的 70%、25%、3% 和 2%。
现在两个人的直接持股比例很小,但我们关心的是最终受益人:最终收到利润的自然人。他们对 A 的最终持股比例实际上仍与原来接近。
最终持股比例按以下过程定义。起初让一家公司获得一笔利润,其他公司的利润为零。每家公司按直接持股比例,将自己收到的钱分给其所有者。自然人收到的钱留在自己手里;公司收到的钱则在下一轮继续分给其所有者。这个过程无限重复,直到所有钱最终分配给自然人。某个人最终得到的钱占初始利润的比例,就是这个人对起始公司的最终持股比例。
给出所有公司的直接持股结构,请求出每个人对每家公司的最终持股比例。
公司按照产业划分为若干行业。同一行业内可以出现任意持股关系,但对于分属不同行业的公司 P 和 Q,下面两件事不能同时发生:
- P 直接或间接持有 Q 的股份;
- Q 直接或间接持有 P 的股份。
可以只发生其中一件,也可以都不发生。每个行业的公司数严格小于 10。输入不提供行业划分。
输入格式
第一行包含两个整数 ,分别表示公司数和自然人数。公司编号为 ,自然人编号为 。
接下来 行,第 行描述第 家公司。该行先给出整数 ,然后给出 个形如“所有者:百分比”的条目:
- Px 表示第 个自然人;
- Cy 表示第 家公司;
- 百分比恰有一位小数,例如 P1:50.0、C2:0.1。
公司可以持有自己的股份。
数据范围与保证
- ;
- ,且 ;
- 自然人编号在 内,公司编号在 内;
- 每项持股百分比大于 、不超过 ,同一家公司的全部持股百分比之和恰为 ;
- 同一家公司的所有者互不相同;
- 每个行业的公司数严格小于 ,行业之间满足上文的持股限制;
- 每家公司至少有一个最终受益的自然人。例如,A 由 B 持股 100%,而 B 又由 A 持股 100% 的封闭结构是不允许的。
输入只有一组数据。
输出格式
输出 行。第 行输出 个实数,第 个数为第 个自然人对第 家公司的最终持股比例。比例的真值在 内;即使某个人没有股份,也要在对应位置输出零。
每个数的绝对误差或相对误差严格小于 时认为正确。同行相邻数用空格分隔。
样例输入 1
2 2
2 P1:50.1 P2:49.9
2 P1:23.4 P2:76.6
样例输出 1
0.501000 0.499000
0.234000 0.766000
样例输入 2
2 2
2 P1:50.0 P2:50.0
3 P1:20.0 P2:30.0 C1:50.0
样例输出 2
0.500000 0.500000
0.450000 0.550000
样例输入 3
2 2
4 P1:1.0 P2:2.0 C2:49.0 C1:48.0
4 C2:70.0 C1:25.0 P1:3.0 P2:2.0
样例输出 3
0.528358 0.471642
0.540299 0.459701
样例输入 4
3 2
5 P1:1.0 P2:2.0 C2:49.0 C1:38.0 C3:10.0
4 C2:70.0 C1:25.0 P1:3.0 P2:2.0
2 P1:20.0 P2:80.0
样例输出 4
0.373228 0.626772
0.411024 0.588976
0.2 0.8