No.210

$p_i, q_i$ は $1000, 100$ で割っておく.

$i$ 番目の部屋を $k$ 回目に探して見つかる確率は, $p_i(1-q_i)^{k-1}q_i$ となる.

見つかる確率が高い部屋から順に探せばいいので, $p_iq_i$ を優先順位付きキューに入れて最も大きいものを取り出し, $(1-q_i)$ を掛けてキューに戻すのを繰り返す.