/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
N 個の押しボタンがあります。このうち 1 個が当たりで、残りの N-1 個はハズレです。
青木君はどのボタンが当たりであるか知っており、高橋君は知りません。また高橋君には N 個のボタンの区別はつきません。
このボタンを使って青木君と高橋君がゲームを行います。ゲームは以下の一連の流れの T 回の繰り返しからなります。
- 青木君が N 個のボタンをランダムな順序に並べる
- 高橋君が「ボタンを 1 つ選び、そのボタンを押す」という操作を M 回行う。同じボタンを複数回選んでもよい
- ゲーム開始時からこれまでに当たりのボタンが何回押されたかを青木君が高橋君に教える
T 回の繰り返しで、当たりのボタンを合計 K 回以上押すことができたとき、かつ、そのときに限り高橋君の勝ちです。
勝つ確率が最大になるように高橋君が行動したときの、高橋君の勝率を求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq T \leq 30
- 1 \leq M \leq 30
- 1 \leq K \leq 30
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N T M K
出力
答えを出力せよ。 真の解との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。
入力例 1
3 2 2 3
出力例 1
0.222222222222222
ゲームは例えば次のように進行します。（最適な行動とは限りません）
- 1回目の繰り返し
- 青木君がボタンをランダムに並び替え、当たりのボタンが 1 番目 、ハズレのボタンが 2,3 番目となる
- 高橋君が 1 番目のボタンを押す
- 高橋君が 2 番目のボタンを押す
- 当たりのボタンが 1 度押されたことを青木君が高橋君に伝える
- 2回目の繰り返し
- 青木君がボタンをランダムに並び替え、当たりのボタンが 3 番目 、ハズレのボタンが 1,2 番目となる
- 高橋君が 3 番目のボタンを押す
- 高橋君が 3 番目のボタンを押す
- 当たりのボタンが 3 度押されたことを青木君が高橋君に伝える
- 当たりのボタンを 3 回以上押したため、高橋君の勝ちです
なお、このケースの真の解は \frac{2}{9} であるため、0.222222 や 0.222223141592 などの出力でも正解と判定されます。
入力例 2
10 1 10 1
出力例 2
1.000000000000000
入力例 3
100 10 10 2
出力例 3
0.401263060761621
Score : 550 points
Problem Statement
There are N push buttons. One of them is the winning button, and the other N-1 are losing buttons.
Aoki knows which button is winning, but Takahashi does not. Also, Takahashi cannot distinguish the N buttons.
They play a game using these buttons. The game consists of repeating the following sequence T times:
- Aoki arranges the N buttons in a random order.
- Takahashi performs the operation “choose a button and press it” M times. He may choose the same button multiple times.
- Aoki tells Takahashi the number of times the winning button has been pressed so far since the start of the game.
Takahashi wins if and only if the winning button has been pressed a total of at least K times throughout the T repetitions.
Find Takahashi’s probability of winning when he plays to maximize his win probability.
Constraints
- 1 \le N \le 2\times 10^5
- 1 \le T \le 30
- 1 \le M \le 30
- 1 \le K \le 30
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N T M K
Output
Output the answer. Your output is considered correct if its absolute or relative error from the true answer is at most 10^{-6}.
Sample Input 1
3 2 2 3
Sample Output 1
0.222222222222222
The game can proceed as follows (not necessarily optimally):
- 1st repetition
- Aoki randomly arranges the buttons so that the winning button is at position 1, and the losing buttons are at positions 2 and 3.
- Takahashi presses button 1.
- Takahashi presses button 2.
- Aoki tells him the winning button has been pressed 1 time.
- 2nd repetition
- Aoki randomly arranges the buttons so that the winning button is at position 3, and the losing buttons are at positions 1 and 2.
- Takahashi presses button 3.
- Takahashi presses button 3.
- Aoki tells him the winning button has been pressed 3 times.
- Since the winning button has been pressed not less than 3 times, Takahashi wins.
The true answer in this case is \tfrac{2}{9}, so outputs like 0.222222 or 0.222223141592 are also accepted.
Sample Input 2
10 1 10 1
Sample Output 2
1.000000000000000
Sample Input 3
100 10 10 2
Sample Output 3
0.401263060761621