#P16801. [NWRRC 2025]Lucky Number Theory

[NWRRC 2025]Lucky Number Theory

L. 幸运数理论()

题目描述

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

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

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

    S:=S+Δ.S:=S+\Delta.
  • 每次按下 Withdraw,机器会向玩家发放

    ⌈S⌉\lceil S\rceil

    张奖券,然后将 SS 重置为 00。

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

Lucy 有足够的游戏币按下 Roll 共 nn 次,并按下 Withdraw 共 kk 次。

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

输入格式

本题包含多组测试数据。

第一行包含一个整数 tt,表示测试数据组数。

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

输出格式

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

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

数据范围

1≤t≤2000,1\le t\le 2000, 1≤k≤n≤2000,1\le k\le n\le 2000, 1≤d≤2000.1\le d\le 2000.

样例

3
3 2 1
5 5 3
7 1 10
2.6250000000
10.0000000000
35.5000000000

样例说明

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

Lucy 首先按下一次 Roll。根据当前的 SS,分为两种情况:

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

    1+32=2.5.1+\frac32=2.5.
  • 如果 S≥12S\ge\frac12,Lucy 应再投掷一次后取票,然后进行最后一次投掷并取票。第一次取票时,有 14\frac14 的概率得到 11 张奖券,有 34\frac34 的概率得到 22 张奖券,因此该情况下的期望奖券数为

    1+2⋅34+1⋅14=2.75.1+2\cdot\frac34+1\cdot\frac14=2.75.

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

12(2.5+2.75)=2.625.\frac12(2.5+2.75)=2.625.

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

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