Hide

Problem H
封筒作りの最適化

Languages en ja sv

プログラミングオリンピック委員会は$N$人で構成されており、全校に予選大会のポスターの入った封筒を送ろうとしています。 手続きを早くするために、作業を分担しています。 作業には、宛名を書く作業、切手を貼る作業、ポスターを入れる作業、封筒を閉じる作業などがあります。 ある人が作業を仕上げると、封筒を別の人に渡します。 なかなか思ったように進まないので、彼らは誰がもっと早く仕事をできるだろうかと考えています。

各人 $p$ は、1 秒あたり $M_ p$ 個の封筒の最大生産速度があります。 人 $p$ に1秒間に送られる封筒の数を$I_ p$、1秒間に仕上げる封筒の数を$U_ p$とすると、$U_ p = \min (I_ p, M_ p)$となります。 また、それ以上の封筒が送られてきたとしても、1秒間に仕上がる数が$M_ p$を超えることはありません。 したがって、各人は、完成した封筒を送る相手を複数持っていることになります。 人 $p$ は、各人に同じ数の封筒を送る必要はありませんが、各人は $p$ が送る封筒のうち一定の割合を受け取ります。 誰からも封筒を送られない人、つまり生産ラインの先頭にいる人は、 $I_ p = \infty $ なので、 $U_ p = M_ p$ となります(無限にある封筒の山からいくらでも受け取れることを意味します)。 中には、それ以上封筒を送らない人もいます。彼らは完成した封筒を積んでおくだけです。

$U_ p = M_ p$ という人、つまり、生産速度を最大にして働いている人は誰でしょうか。

入力

最初の行には整数の $1 \le N \le 10^5$ が含まれます。これは、人数を表します。 次の$N$行は、それぞれの人を表します。$i$行目は、人$i$の最大生産速度 $M_ i$ ($1 \le M_ i \le 10^5$) から始まります。 そのあとに、整数$k$があり、さらに後に $k$対の整数$j$ $w$があります。これは、人$i$は、封筒の$w$パーセントを人$j$に送ることを表します。($1 \le w \le 100$, $1 \le j \le N, i \neq j$) 同じ$j$の値が1行に複数回出てくることはありません。$k = 0$でない限り、各行の$w$の値の合計は$100$となります。

全ての$k$の合計 $S$ は、$0 \le S \le 10^5$ を満たします。

一連の工程は、すでに作業を行った封筒が同じ人に戻されることはないように設計されています。

出力

$U_ p = M_ p$を満たすすべての $i$ を、昇順で1行に表示します。

$U_ p = M_ p$ の場合は、余裕をもっていることが保証されています。 より具体的には $I_ p - M_ p > 10^{-4}$ となります。

一方、もし $U_ p \neq M_ p$ ならば、$M_ p - I_ p > 10^{-4}$ となります。

得点

あなたのソリューションは、いくつかのテストケースグループでテストされます。 グループのポイントを得るためには、グループ内のすべてのテストケースに成功しなければなりません。

Group

Point value

Bounds

$1$

$12$

それぞれの人が最大1人の人に封筒を送り(つまり、$k \leq 1$)、最大1人の人から封筒を受け取ります。

$2$

$17$

それぞれの人は、封筒を受け取らない人 $1$ を除いて、他の人1名から手紙を受け取ります。

$3$

$21$

$i$ が人 $j$ に封筒を送るなら、$i < j$ です。

$4$

$25$

$N, S \le 10$

$5$

$25$

追加の制約はありません。

サンプルの説明

ここでは、3つの例を表すグラフを示します。各人をノードで表しています。それぞれの辺には、封筒の送信数を「ps」という単位で、1秒あたりの封筒数を書いています。

テストケースグループ$1$ではサンプルケース$1$のみ、テストケースグループ$2$ではサンプルケース$2$のみ、テストケースグループ$3$ではサンプルケース$3$のみが 発生する可能性があることに注意してください。

テストケースグループ$4$$5$では、3つの例のケースすべてが発生する可能性があります。

\includegraphics[width=0.8\textwidth ]{sample1}
図 1: Sample $1$
\includegraphics[width=0.8\textwidth ]{sample2}
図 2: Sample $2$
\includegraphics[width=0.8\textwidth ]{sample3}
図 3: Sample $3$
サンプル入力 1 サンプル出力 1
8
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
サンプル入力 2 サンプル出力 2
10
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
サンプル入力 3 サンプル出力 3
6
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