Problem H
Letter Optimization

The programming olympiad committee, composed of $N$ people, is going to send out envelopes with posters for the qualifier competition to all schools. To make the process faster, they have split up the tasks that need to be done. The tasks include writing addresses, putting on stamps, inserting the posters, and closing the envelopes. When a person finishes an envelope, it is sent to another person. It’s not going as fast as they had hoped, so they wonder which people could be working faster.

Each person $p$ has their own maximum production speed of $M_ p$ envelopes per second. If we let $I_ p$ be the number of envelopes are sent to person $p$ per second, and let $U_ p$ be the number of envelopes that are finished per second, then $U_ p = \min (I_ p, M_ p)$. A person also cannot finish more than $M_ p$ letters per second, even if they get more to work with. Therefore, each person has a number of people to whom they send their finished envelopes. Person $p$ is not required to send the same number of envelopes to each person, but each person receives a certain percentage of the envelopes $p$ sends. The people to whom no one sends any envelopes, and are therefore at the beginning of the production line, have $I_ p = \infty $, and therefore $U_ p = M_ p$ (they have an infinite pile of envelopes to work from). Certain people do not send envelopes any further; they just put them into a pile beside them when they are done.

Which people have the property that $U_ p = M_ p$, that is, they are working at their maximum production speed?


The first line contains an integer $1 \le N \le 10^5$, the number of people. The next $N$ lines describe the people. Line $i$ begins with the integer $M_ i$, the maximum production speed of person $i$ ($1 \le M_ i \le 10^5$). After that comes an integer $k$, and then $k$ pairs of integers $j$ $w$, which means that person $i$ sends $w$ percent of their envelopes to person $j$ ($1 \le w \le 100$, $1 \le j \le N, i \neq j$). No $j$ can appear more than once per line, and the sum of the $w$ values on each line is $100$, unless $k = 0$.

Let $S$ be the sum of all $k$. Then $0 \le S \le 10^5$.

The production chain is designed in such a way that no person can get back a letter they have already worked on.


Print a line with all $i$ that fulfill $U_ p = M_ p$, in increasing order.

It’s guaranteed that if $U_ p = M_ p$, then this will be true with a margin, more specifically $I_ p - M_ p > 10^{-4}$.

If, on the other hand, $U_ p \neq M_ p$, then there is a margin in the other direction: $M_ p - I_ p > 10^{-4}$.


Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.


Point value




Each person sends letters to at most one person (i.e. $k \leq 1$) and receives letters from at most one person.



Each person receives letters from exactly one other person, except person $1$ who doesn’t receive any letters.



If person $i$ sends to person $j$, then $i < j$.



$N, S \le 10$



No additional constraints.

Explanation of test case

Here are three graphs that represent the three example cases. Each person is represented by a node. On each edge, the number of envelopes sent is written in the unit "ps", envelopes per second.

Note that in test case group $1$, only sample case $1$ could occur, in test case group $2$ only example case $2$, and in test case group $3$ only example case $3$.

In test case groups $4$ and $5$, all three example cases could occur.

\includegraphics[width=0.8\textwidth ]{sample1}
Figure 1: Sample $1$
\includegraphics[width=0.8\textwidth ]{sample2}
Figure 2: Sample $2$
\includegraphics[width=0.8\textwidth ]{sample3}
Figure 3: Sample $3$
Sample Input 1 Sample Output 1
7 0
10 1 6 100
8 1 4 100
9 1 1 100
11 0
12 1 5 100
10 1 3 100
5 0
1 2 3 7 8
Sample Input 2 Sample Output 2
16 3 2 50 4 25 6 25
9 2 9 75 5 25
2 1 8 100
5 0
1 0
2 2 3 90 7 10
1 0
1 0
5 1 10 100
6 0
1 5 6 8 9
Sample Input 3 Sample Output 3
10 3 2 25 3 25 4 50
1000 1 5 100
1000 1 5 100
1000 1 6 100
1 1 6 100
1000 0
1 5
CPU Time limit 2 seconds
Memory limit 1024 MB
Statistics Show
Languages English, 日本語, Svenska
Nicole Hedblom
Source Programmeringsolympiadens onlinekval 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in