L. 幸运数理论（）

题目描述

Lucy 经常去游戏厅。游戏厅里的机器会发放奖券，奖券可以兑换奖品。Lucy 最喜欢的一台机器有两个按钮：Roll 和 Withdraw。

机器内部维护一个实数 $S$，初始时 $S=0$。

• 每次按下 Roll，机器都会独立生成一个在开区间 $(0,d)$ 上均匀分布的随机实数 $\Delta$，然后令

  $$S:=S+\Delta.$$

• 每次按下 Withdraw，机器会向玩家发放

  $$\lceil S\rceil$$

  张奖券，然后将 $S$ 重置为 $0$。

Lucy 可以随时以任意精度观察屏幕上的 $S$，并根据当前值决定接下来按 Roll 还是 Withdraw。

Lucy 有足够的游戏币按下 Roll 共 $n$ 次，并按下 Withdraw 共 $k$ 次。

请制定一种最优策略，使 Lucy 获得的奖券数量期望最大，并输出这个最大期望值。

输入格式

本题包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数。

每组测试数据包含一行三个整数 $n,k,d$，分别表示可按 Roll 的次数、可按 Withdraw 的次数，以及每次随机增量的上界。

输出格式

对于每组测试数据，输出 Lucy 在最优策略下能够获得的最大奖券数期望。

答案的绝对误差或相对误差不超过 $10^{-6}$ 即可。

数据范围

样例

3
3 2 1
5 5 3
7 1 10

2.6250000000
10.0000000000
35.5000000000

样例说明

在第一组测试数据中，$n=3$、$k=2$、$d=1$。

Lucy 首先按下一次 Roll。根据当前的 $S$，分为两种情况：

• 如果 $S<\frac12$，Lucy 应立即取票，然后再连续投掷两次，最后再次取票。该情况下的期望奖券数为

  $$1+\frac32=2.5.$$

• 如果 $S\ge\frac12$，Lucy 应再投掷一次后取票，然后进行最后一次投掷并取票。第一次取票时，有 $\frac14$ 的概率得到 $1$ 张奖券，有 $\frac34$ 的概率得到 $2$ 张奖券，因此该情况下的期望奖券数为

  $$1+2\cdot\frac34+1\cdot\frac14=2.75.$$

两种情况发生的概率都为 $\frac12$，所以总期望为

在第二组测试数据中，Lucy 可以在每次投掷后立即取票，每次平均获得 $2$ 张奖券。

在第三组测试数据中，Lucy 只能取票一次，因此应在完成全部 $7$ 次投掷后取票。