P1475 [USACO2.3] Controlling Companies

Some companies are partial owners of other companies because they own a portion of the shares issued by those companies. It is said that if at least one of the following three conditions is met, company $A$ can control company $B$: - Company $A$ = company $B$. - Company $A$ owns more than $50\%$ of company $B$'s stock. - Company $A$ controls $K$ ($K \geq 1$) companies, denoted $C_1, \ldots, C_K$, each company $C_i$ owns $x_i\%$ of company $B$'s stock, and $x_1+ \ldots + x_K \gt 50\%$. You are given a table where each row contains three numbers $i,j,p$: it means company $i$ owns $p\%$ of company $j$. Compute all pairs $(h,s)$ indicating that company $h$ controls company $s$. There are at most $100$ companies.

The first line contains an integer $N$, the number of rows in the table. Each of the next $N$ lines contains three integers $i,j,p$, meaning company $i$ owns $p\%$ of company $j$'s stock.

Output zero or more companies that control other companies. Each line contains two integers $A,B$, meaning company $A$ controls company $B$. Sort the output pairs in ascending order by $A$ as the primary key and $B$ as the secondary key. Do not output cases where a company controls itself (i.e., all pairs must satisfy $A \neq B$).

Translated from NOCOW. USACO 2.3. Translated by ChatGPT 5