問題一覧 > 通常問題

No.210 探し物はどこですか?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-3}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 78
作問者 : autotaker1984autotaker1984
10 ProblemId : 483 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-01-11 20:32:22

問題文

探偵のコーデリアは老紳士から紛失したメガネの捜索を依頼された。
老紳士の邸宅には部屋が$n$個あり、それぞれの部屋に$1$から$n$までの番号がふってある。そのうち$i$番目の部屋でメガネを紛失した確率は$\frac{p_i}{1000}$であることがわかっている。
また部屋は非常に散らかっておりその部屋にメガネがあっても一回捜索しただけでメガネが見つかるとは限らない。
$i$番目の部屋にメガネがあった時、過去に何回その部屋を捜索したかに関係なくその部屋を一回捜索してメガネが見つかる確率は$\frac{q_i}{100}$である。

コーデリアは茉莉音のライブに参加するため、できるだけ少ない回数、部屋を捜索してメガネを見つけたい。
コーデリアを助けるため、メガネが見つかるまでに部屋を捜索する回数の期待値を最小化してほしい。

入力

$n$
$p_1\ p_2\ \dots\ p_n$
$q_1\ q_2\ \dots\ q_n$


一行目には部屋の数が与えられる。
二行目には$n$個の整数が与えられる。各部屋でメガネを紛失した確率を1000倍した値である。
三行目には$n$個の整数が与えられる。各部屋を一回捜索したときにメガネが見つかる確率を100倍した値である。
$1 \leq n \leq 1000$
$0 \leq p_i \leq 1000$
$1 \leq q_i \leq 100$
$\sum_{i = 1}^n p_i = 1000$

出力


コーデリアがメガネが見つけるまでに部屋を捜索する回数の期待値の最小値を出力せよ。相対誤差あるいは絶対誤差は0.001まで許される。
最後に改行してください。

サンプル

サンプル1
入力
1
1000
50
出力
2.0


この例では探すべき部屋は一つしかありません。
この場合の期待値は$E = \sum_{k=1}^{\infty} k 0.5^{k} = 2$です。

サンプル2
入力
10
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
出力
5.5


この例では各部屋を一回捜索すれば確実にメガネを発見できます。
どの部屋にあるかは同様に確からしいので、
コーデリアはどの順番で部屋を捜索しても期待値は変わりません。

サンプル3
入力
10
64 201 4 30 232 64 197 7 102 99
28 43 94 52 24 33 97 55 36 89
出力
12.277056

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。