Money Laundering
Description
Consider a company $A$ that made a 100€ of profit this year. The company's owners are Ivan with $52.8\%$ ownership share and Robi with a $47.2\%$ ownership share. Naturally, the profits are shared proportionally to the shares with Ivan receiving 52.8€ and Robi 47.2€.
They will have to pay tax on the received profits, but would like to avoid doing so, if at all possible. Sadly, the ownership structure of their company is too simple and it's easily discoverable how much profits each of them received.
For the next year, they prepare a plan. They make a shell company $B$ and change the ownership shares. Ivan now only owns $1\%$ of company $A$, Robi only $2\%$, the company $B$ owns a $49\%$ share of $A$ and $A$ owns $48\%$ of itself. Company $B$ has a similar ownership structure. $70\%$ ownership share belongs to $B$ itself, $25\%$ to $A$, $3\%$ to Ivan and $2\%$ to Robi.
Looking naively, Ivan and Robi have very small ownership shares. However, we are interested in the ownership shares of ultimate beneficial owners, the persons who will ultimately profit, which are Ivan and Robi in our case. We wish to determine their ultimate ownership shares, which turn out to be approximately equal to what they were before the introduction of $B$.
Ultimate ownership shares can be determined as follows: let the company $A$ have 100€ of profit and $B$ have 0€. The profits are paid out to all direct owners in proportion to their ownership share. However, since $A$ and $B$ are partial owners of themselves, they receive a part of the profit. To determine the ultimate share of the ultimate beneficial owners, we repeat the procedure – any profits that $A$ and $B$ receive are paid out again, with Ivan and Robi getting a share, as well as $A$ and $B$. This is repeated ad infinitum until (theoretically, after an infinite number of steps) all money is paid out to the ultimate beneficial owners, and the ratio of the final sums received by Ivan and Robi is by definition equal to their ultimate share of $A$.
For a given structure of companies, determine the shares of the ultimate beneficial owners. However, the companies do not form a random network of ownership, but are structured in industrial sectors. Companies within sectors may form arbitrary ownership structures, but this is not true for companies in different sectors. If companies $P$ and $Q$ belong to different sectors, it cannot happen that
- $P$ would own a (potentially indirect) share of $Q$ and
- $Q$ would own a (potentially indirect) share of $P$.
One or none of these statements could be true, but not both.
The first line contains two space-separated integers $c$ and $p$, representing the number of companies and number of persons, respectively. Then $c$ lines follow, and $i$-th of them contains the description of $i$-th company. The line contains an integer $k_i$, the number of owners, and then $k_i$ entries of the form $o_{i,j}\,\colon\, p_{i, j}$, where $o_{i,j}$ is the designation of the $j$-th owner (person or company) and $p_{i, j}$ is their share in percentages. The share will have exactly one decimal place.
Input limits
- $1 \leq c, p \leq 10^3$
- $1 \leq \sum_{i=1}^n k_i \leq 10^4$
- $o_{i,j}$ can have two forms: $\texttt{P}x$ or $\texttt{C}y$, indicating that the owner is the $x$-th person or $y$-th company, respectively. It is guaranteed that $1 \leq x \leq p$, and $1 \leq y \leq c$ holds.
- $k_i \geq 1$
- $0 < p_{i,j} \leq 100$
- $\sum_{j=1}^{k_i} p_{i,j} = 100$
- The identifiers $\{o_{i,j}\}_{j=1}^{k_i}$ are unique, i.e. each owner is listed at most once.
- The number of companies belonging to each sector is less than $10$.
- Each company has at least one ultimate beneficial owner. For example, a scheme where $A$ would own a $100\%$ of $B$ and $B$ a $100\%$ of $A$ is forbidden.
Output the ultimate ownership shares of all persons in all companies. The $i$-th line should include shares of all persons in the $i$-th company, including persons with no share. The share is between $0$ and $1$. Shares in a line should be separated by a space. The answer will be considered correct if its absolute or relative error is less than $10^{-4}$.
Input
The first line contains two space-separated integers $c$ and $p$, representing the number of companies and number of persons, respectively. Then $c$ lines follow, and $i$-th of them contains the description of $i$-th company. The line contains an integer $k_i$, the number of owners, and then $k_i$ entries of the form $o_{i,j}\,\colon\, p_{i, j}$, where $o_{i,j}$ is the designation of the $j$-th owner (person or company) and $p_{i, j}$ is their share in percentages. The share will have exactly one decimal place.
Input limits
- $1 \leq c, p \leq 10^3$
- $1 \leq \sum_{i=1}^n k_i \leq 10^4$
- $o_{i,j}$ can have two forms: $\texttt{P}x$ or $\texttt{C}y$, indicating that the owner is the $x$-th person or $y$-th company, respectively. It is guaranteed that $1 \leq x \leq p$, and $1 \leq y \leq c$ holds.
- $k_i \geq 1$
- $0 < p_{i,j} \leq 100$
- $\sum_{j=1}^{k_i} p_{i,j} = 100$
- The identifiers $\{o_{i,j}\}_{j=1}^{k_i}$ are unique, i.e. each owner is listed at most once.
- The number of companies belonging to each sector is less than $10$.
- Each company has at least one ultimate beneficial owner. For example, a scheme where $A$ would own a $100\%$ of $B$ and $B$ a $100\%$ of $A$ is forbidden.
Output
Output the ultimate ownership shares of all persons in all companies. The $i$-th line should include shares of all persons in the $i$-th company, including persons with no share. The share is between $0$ and $1$. Shares in a line should be separated by a space. The answer will be considered correct if its absolute or relative error is less than $10^{-4}$.
2 2
2 P1:50.1 P2:49.9
2 P1:23.4 P2:76.6
2 2
2 P1:50.0 P2:50.0
3 P1:20.0 P2:30.0 C1:50.0
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 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
0.501000 0.499000
0.234000 0.766000
0.500000 0.500000
0.450000 0.550000
0.528358 0.471642
0.540299 0.459701
0.373228 0.626772
0.411024 0.588976
0.2 0.8