/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
私は通勤電車のエキスパートである。今日も駅のホームで電車を待っているところだ。待っている電車はこの駅が始発なので、席はすべて空いているが、自分より前に N 人の人が列をなしているので座れるかどうかは分からない。
車両には K 個の席が一直線に並んでおり、それぞれ席 1 から席 K までの連続する整数の番号がふられている。席の数と自分の前に並んでいる人数が分かれば、座れるかどうかが分かるのではないかと思われるかもしれないが、ことはそう単純ではないのである。
人はその日の気分によって座る席をどのように選ぶかが変わるということを私は知っている。具体的には、ある日の気分は次の 2 通りである。
- 「とにかく座りたい気分」 : この気分の人は、空いている席がひとつでもあれば、そのうち番号が最も小さい席に座る。
- 「余裕があれば座りたい気分」 : この気分の人は、空いている席のなかで、両隣の席も空いているようなものがあれば、そのうち番号が最も小さい席に座る。なお、隣の席が存在しない場合も、隣の席が空いていると見做してよい。
いずれの気分のときでも、座る条件を満たす席がない場合は席に座るのを諦める。
さて、いま私の前に並んでいる人たちを先頭から順に人 1, 人 2, ……, 人 N と番号づけることにする。つまり、まず人 1 が車両に入り、その日の気分に従って席を選ぶ。次に人 2 が車両に入り、その日の気分に従って席を選ぶ。これを繰り返して人 N が車両に入り、席を選び終えたらようやく私が車両に入る。
私の見立てでは、人 i は p_i パーセントの確率で「とにかく座りたい気分」になり、100 - p_i パーセントの確率で「余裕があれば座りたい気分」になる。この仮定のもとで、人 N までが車両に入って席を選び終えたとき、つまり、私が車両に入ったときに空いている席の個数の期待値がいくつになるかを計算したい。
入力
N K p_1 p_2 : p_N
- 1 行目には、列に並んでいる人数を表す整数 N (1 ≦ N ≦ 100) と、車両にある席の個数を表す整数 K (1 ≦ K ≦ 200) が書かれている。
- 2 行目から N 行にわたって、それぞれの人の情報が与えられる。このうち i 行目には、人 i が「とにかく座りたい気分」になる確率を表す整数 p_i (0 ≦ p_i ≦ 100) が書かれている。
部分点
この問題には部分点が設定されています。
- N ≦ 10 を満たすデータセットにすべて正解すると 30 点が得られます。
- すべてのデータセットに正解すると、上に加えてさらに 70 点が得られ、全体で 100 点が得られます。
出力
人 N が車両に入り席を選び終えた時点での、空いている席の個数の期待値を表す実数を 1 行に出力せよ。真の値との絶対誤差または相対誤差が 10^{-6} 以下であれば正答とみなす。
入力例1
3 4 100 30 60
出力例1
1.28
人 1 は常に「とにかく座りたい気分」なので、人 2, 3 の気分について考えると
- 人 2, 3 の両方が「とにかく座りたい気分」になる確率は 0.3 \times 0.6 = 0.18 で、空席は 1 個になります。
- 人 2 は「とにかく座りたい気分」だが人 3 は「余裕があれば座りたい気分」になる確率は 0.3 \times 0.4 = 0.12 で、空席は 1 個になります。
- 人 2 は「余裕があれば座りたい気分」だが人 3 は「とにかく座りたい気分」になる確率は 0.7 \times 0.6 = 0.42 で、空席は 1 個になります。
- 人 2, 3 の両方が「余裕があれば座りたい気分」になる確率は 0.7 \times 0.4 = 0.28 で、空席は 2 個になります。
したがって、空いている席の個数の期待値は 1 \times 0.18 + 1 \times 0.12 + 1 \times 0.42 + 2 \times 0.28 = 1.28 となります。
入力例2
5 7 28 31 59 61 30
出力例2
2.11193
入力例3
10 10 97 98 99 98 97 96 97 98 99 98
出力例3
0.020237732