分数: 450 点
问题陈述
给你一个整数 N。您可以执行以下两种类型的操作:
- 支付 X 日元更换 N 与 \displaystyle\left\lfloor\frac{N}{A}\right\rfloor.
- 支付 Y 日元掷骰子(骰子),显示之间的整数 1 和 6,包含在内,概率相等。让 b 成为骰子的结果,并替换 N 与 \displaystyle\left\lfloor\frac{N}{b}\right\rfloor.
在这里, \lfloor s \rfloor 表示小于或等于的最大整数 s。例如, \lfloor 3 \rfloor=3 和 \lfloor 2.5 \rfloor=2.
确定之前支付的最低预期成本 N 变为 0 最佳选择操作时。
每次操作中骰子的结果与其他辊无关,可以在观察之前操作的结果后做出操作的选择。
约束
- 1 \leq N \leq 10^{18}
- 2 \leq A \leq 6
- 1 \leq X, Y \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A X Y
输出
打印答案。
如果真实答案的绝对或相对误差最多为,则您的输出将被视为正确 10^{-6}.
示例输入 1
3 2 10 20
示例输出 1
20.000000000000000
可用的操作如下:
- 支付 10 日元。更换 N 与 \displaystyle\left\lfloor\frac{N}{2}\right\rfloor.
- 支付 20 日元。掷骰子。让 b 为结果,并替换 N 与 \displaystyle\left\lfloor\frac{N}{b}\right\rfloor.
最佳策略是执行第一个操作两次。
示例输入 2
3 2 20 20
示例输出 2
32.000000000000000
可用的操作如下:
- 支付 20 日元。更换 N 与 \displaystyle\left\lfloor\frac{N}{2}\right\rfloor.
- 支付 20 日元。掷骰子。让 b 为结果,并替换 N 与 \displaystyle\left\lfloor\frac{N}{b}\right\rfloor.
最优策略如下:
- 首先,执行第二个操作来掷骰子。
- 如果结果是 4 或更大,则 N 变为 0.
- 如果结果是 2 or 3,然后 N 变为 1。现在,执行第一个操作 N = 0.
- 如果结果是 1,从头开始。
示例输入 3
314159265358979323 4 223606797 173205080
示例输出 3
6418410657.7408381