35029번 - Lucky Number Theory 스페셜 저지다국어

문제

Lucy is a frequent arcade visitor. All machines at the arcade give out tickets to exchange for prizes! Lucy's favorite machine works as follows.

The machine only has two buttons: "Roll" and "Withdraw". Whenever Lucy presses "Roll", the machine increases the counter on the screen by a randomly generated real number between 0ドル$ and $d$. At any moment, she can press "Withdraw" to get the number of tickets equal to the counter, which gets reset. In case it's not an integer, the machine generously rounds the counter up before handing out the tickets.

More formally, the machine stores a real number $S,ドル initially equal to 0. On each "Roll" press, the machine generates $\Delta$ --- a random real number picked uniformly from the interval $(0, d)$. Then, $S$ increases by the value of $\Delta$. When the "Withdraw" button is pressed, the machine rounds $S$ up, giving the player $\lceil S \rceil$ tickets, and then resets $S$ back to zero. Lucy can see the value of $S$ on the screen at any moment with as much precision as she wants, and she can use it to decide whether to roll or withdraw.

Lucy has enough arcade tokens to press "Roll" $n$ times, and "Withdraw" $k$ times. Find a strategy that maximizes the expected number of tickets Lucy can get, and print this maximum expected number.

입력

Each test contains multiple test cases. The first line contains the number of test cases $t$ (1ドル \le t \le 2000$). The description of the test cases follows.

The only line of each test case contains three integers $n,ドル $k,ドル and $d,ドル denoting the number of rolls, the number of withdrawals, and the upper bound on roll values (1ドル \le k \le n \le 2000$; 1ドル \le d \le 2000$).

출력

For each test case, print the maximum expected number of tickets Lucy can get, as a floating point number. Your answer will be considered correct if its absolute or relative error doesn't exceed 10ドル^{-6}$.

제한

노트

In the first test case, with $n = 3$ rolls, $k = 2$ withdrawals, and $d = 1,ドル the optimal strategy is as follows:

Lucy starts with a roll. Depending on the number $S,ドル there are two possibilities:

• The number is less than $\frac 12$. In this case, Lucy should withdraw, then roll two more times, and withdraw at the end. The expected number of tickets in this case is 1ドル + \frac 32 = 2.5$ (1ドル$ ticket for the first withdrawal, and $\frac 32$ tickets on average after two rolls).
• The number is at least $\frac 12$. In this case, it's optimal to roll again, withdraw, then roll for the last time, and withdraw at the end. For the first withdrawal, she will get only one ticket with probability $\frac 14$ (the probability that the sum of the first two rolls is at most 1, given that the first roll was over $\frac 12$), and two tickets with probability $\frac 34$. The expected number of tickets is 1ドル + 2 \cdot \frac 34 + 1 \cdot \frac 14 = 2.75$.

Each case happens with probability $\frac 12,ドル so the total expected value for this strategy is $\frac 12 (2.5 + 2.75) = 2.625$.

In the second test case, Lucy can withdraw after every roll, each time getting 2ドル$ tickets on average.

In the third test case, Lucy can only withdraw once, and she should do it after all 7ドル$ rolls.