/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
あなたとディーラーでゲームをします。 ゲームは 1 以上 D 以下の整数が等確率で出る D 面サイコロ、0 で初期化された変数 x,y を用いて以下のように行われます。
-
あなたはサイコロを振り、出た目を x に加算する操作を好きな回数行える。ここで、あなたは操作を行うたびに次の操作を行うかを選択できる。
-
その後、ディーラーは y < L を満たす限り、サイコロを振り、出た目を y に加算する操作を繰り返す。
-
x > N の場合あなたの負けである。そうでない場合、y > N または x>y のいずれかを満たす場合あなたの勝ちで、どちらも満たさない場合あなたの負けである。
あなたが勝率を最大化するように適切に行動する際、勝率を求めてください。
制約
- 入力は全て整数
- 1\leq L\leq N\leq 2\times 10^5
- 1\leq D \leq N
入力
入力は以下の形式で標準入力から与えられる。
N L D
出力
答えを出力せよ。出力した値の真の値との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。
入力例 1
3 2 2
出力例 1
0.468750000000000
x が 2 以下の場合操作を続けるという戦略が最適であることが証明できます。
入力例 2
200000 200000 200000
出力例 2
0.999986408692793
Score: 550 points
Problem Statement
You will play a game against a dealer. The game uses a D-sided die (dice) that shows an integer from 1 to D with equal probability, and two variables x and y initialized to 0. The game proceeds as follows:
-
You may perform the following operation any number of times: roll the die and add the result to x. You can choose whether to continue rolling or not after each roll.
-
Then, the dealer will repeat the following operation as long as y < L: roll the die and add the result to y.
-
If x > N, you lose. Otherwise, you win if y > N or x > y and lose if neither is satisfied.
Determine the probability of your winning when you act in a way that maximizes the probability of winning.
Constraints
- All inputs are integers.
- 1 \leq L \leq N \leq 2 \times 10^5
- 1 \leq D \leq N
Input
The input is given from Standard Input in the following format:
N L D
Output
Print the answer. Your output will be considered correct if its absolute or relative error from the true value is at most 10^{-6}.
Sample Input 1
3 2 2
Sample Output 1
0.468750000000000
It can be proved that the optimal strategy is to continue rolling as long as x is not greater than 2.
Sample Input 2
200000 200000 200000
Sample Output 2
0.999986408692793