/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 475 点
問題文
N 枚のカードが入ったパックが無限にあります。各パックについて、i 枚目に入っているカードは P_i\% の確率でレアです。また、各カードがレアであることは他のカードがレアであることと独立です。
これからパックを一つずつ開封していき、開封したパックに入っているすべてのカードを手に入れます。レアカードを合計 X 枚以上手に入れるまでパックを開封するとき、開封するパックの個数の期待値を求めてください。
制約
- 1 \leq N \leq 5000
- 1 \leq X \leq 5000
- 1 \leq P_i \leq 100
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X P_1 P_2 \ldots P_N
出力
答えを出力せよ。
真の答えとの絶対誤差または相対誤差が 10^{-6} 以下ならば正解と判定される。
入力例 1
2 2 50 100
出力例 1
1.5000000000000000
開封するパックの個数は \frac{1}{2} の確率で 1 個、\frac{1}{2} の確率で 2 個となります。
入力例 2
2 3 40 60
出力例 2
3.2475579530543811
入力例 3
6 3 10 33 33 10 100 10
出力例 3
1.8657859189536100
Score: 475 points
Problem Statement
There are infinitely many packs, each containing N cards. In each pack, the i-th card is rare with probability P_i percent. Whether each card is rare is independent of other cards being rare.
You will now open the packs one by one, and obtain all the cards in each opened pack. When you keep opening packs until you have obtained a total of at least X rare cards, find the expected number of packs you will open.
Constraints
- 1 \leq N \leq 5000
- 1 \leq X \leq 5000
- 1 \leq P_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X P_1 P_2 \ldots P_N
Output
Print the answer.
Your answer will be considered correct if the absolute or relative error from the true answer is at most 10^{-6}.
Sample Input 1
2 2 50 100
Sample Output 1
1.5000000000000000
The number of packs opened will be 1 with probability \frac{1}{2}, and 2 with probability \frac{1}{2}.
Sample Input 2
2 3 40 60
Sample Output 2
3.2475579530543811
Sample Input 3
6 3 10 33 33 10 100 10
Sample Output 3
1.8657859189536100