Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 700 点
問題文
現在のパ研では、「打鍵戦争」というゲームが流行っています。パ研には N 人の部員がいますが、その中から「打鍵戦争」という大会に K (2K \leq N) 人の代表選手を出すことになりました。
各部員には、「打鍵力」という値が定まっており、部員 i の打鍵力は A_i で、この値が等しいような部員の組は存在しません。
現在パ研では、「打鍵力」の小さい方から K 人が「代表候補」として選ばれています。
パ研の主将であるあなたは、以下の操作を 0 回以上行います。
- その時点で代表候補である部員 i、代表候補でない部員 j を自由に選び、対戦させる。
- 部員 i は確率 \frac{A_i}{A_i+A_j} で勝ち、部員 j は確率 \frac{A_j}{A_i+A_j} で勝つ。
- その時点で代表候補である部員 i が勝った場合何も起こらない。
- その時点で代表候補でない部員 j が勝った場合、部員 j が新たに代表候補となり、部員 i は代表候補から外れる。
あなたが対戦をさせるのをやめた時点で代表候補である部員たちが、そのまま代表選手となります。
あなたは、できるだけ少ない回数の対戦を行うことで、代表選手の打鍵力の和を最大化したいと思っています。対戦回数の期待値を最小化するように対戦させたとき、代表選手の打鍵力の和が最大になるまで何回の対戦が必要でしょうか。その期待値を求めてください。
制約
- 入力は全て整数である。
- 2 \leq N \leq 10^5
- 1 \leq 2K \leq N
- 1 \leq A_i \leq 10^9
- A_i \neq A_j(i \neq j)
入力
入力は以下の形式で標準入力から与えられます。
N K
A_1 A_2 ... A_{N-1} A_N
出力
対戦回数の期待値の最小値を出力してください。
絶対誤差または相対誤差が 10^{-9} 以内ならば正解となります。
入力例1
2 1
42 8
出力例1
1.190476190476
部員 1 と部員 2 を、部員 1 が勝つまでひたすら対戦させるしかありません。
このときの対戦回数の期待値は、 \frac{25}{21} = 1.190476... 回となります。
入力例2
5 1
3 9 4 2 8
出力例2
1.222222222222
入力例3
10 5
20 3 9 5 8 1 100 32 7 2
出力例3
5.723472222222
writer: TAISA_