No.475 最終日 - Writerの怠慢

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 25
作問者 : chaemonchaemon / テスター : 🐬hec🐬hec

0 ProblemId : 131 / 出題時の順位表

Note

メリークリスマス♪
本日はAdvent Calendar Contestの最終日です。
実際に問題文のような順位の決定がなされることはありません。

問題文

私はAdvent Calendar Contestの最終日を担当することになった。しかし、クリスマスを楽しみすぎたため、問題を考えるのを忘れ、気がついたら出題時刻になってしまった。そこで、最終日は問題を出題せず、ランダムに順位を決定することにした。

すなわち、まだACとなっていない参加者(Writerを除く)から一人をランダムに選んでその参加者をAC扱いとするという手順を全員ACとなるまで繰り返して順位を決定するという暴挙に出た。なお、Testerはいないものとする。

最終日の問題の★の数が$S$個で、その問題の順位が$R$位であった場合、$\left\lfloor 50S+\frac{50S}{0.8+0.2R}\right\rfloor$点が与えられる。Writerには、無条件で$100S$点が与えられる。

各コンテスト参加者の前日までの得点と、最終日の問題の★の数が入力されるので、私(Writer)が優勝できる確率を求めてほしい。

ただし、優勝とは最終日の得点と前日までの合計得点を足した合計点が参加者中で最高となることをいい、同立で最高得点の場合も優勝とみなす。

入力

$N$ $S$ $writer\_id$
$a_0$ $a_1$ $a_2$ $a_3$ $\cdots$ $a_{N-1}$


入力は全て整数で与えられる。
$N$はコンテスト参加者の人数、$S$は★の数であり、各参加者には0から始まるid, $0,1,\ldots, N-1$が付与されている。$a_i$はid$i$の参加者の前日までの合計得点を表し、$writer\_id$はWriter(私)のidを表す。

$3\leqq N\leqq 77777$
$1\leqq S\leqq 500000$
$0\leqq a_i\leqq 100000000$

出力


出力は1行で私が優勝できる確率を出力せよ。絶対誤差または相対誤差が$10^{-9}$以下の誤差は許容される。

最後の改行を忘れずに。

サンプル

サンプル1
入力
3 3 0
1 0 2
出力
0.5


最終日の問題は★3つで順位が高い順に300点、275点が与えられる。

Writerは$1+300=301$点。id1の参加者が1位、id2の参加者が2位であれば、私は優勝できる。

サンプル2
入力
3 3 0
2 2 2
出力
1.0


Writerは300点もらえるが、残り2人のどちらが最終日で1位になってもWriterは優勝できる。

サンプル3
入力
20 3 5
6834 6368 6098 5975 5962 5516 5453 5102 4866 4692 4679 4652 4650 4481 4324 4181 4150 3934 3784 3628
出力
0.0


このデータは12月24日午後9時時点での実際の上位20人のデータであり、$writer\_id$には私を指定した。このルールでも私が優勝する確率は0.0とのことらしい。とほほ。。。

提出ページヘ