AT_abc350_e [ABC350E] Toward 0

题目描述

给定一个整数 $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$ 所需支付金额的期望值的最小值。 注意，每次掷骰子的结果都是独立的，并且你可以在每次操作后根据结果决定下一步操作。

输入格式

输入以如下格式从标准输入读入：

$N$ $A$ $X$ $Y$

输出格式

请输出答案。 当你的答案与真值的绝对误差或相对误差不超过 $10^{-6}$ 时，将被判定为正确。

输入输出样例 #1

输入 #1

3 2 10 20

输出 #1

20.000000000000000

输入输出样例 #2

输入 #2

3 2 20 20

输出 #2

32.000000000000000

输入输出样例 #3

输入 #3

314159265358979323 4 223606797 173205080

输出 #3

6418410657.7408381

说明/提示

限制条件

• $1 \leq N \leq 10^{18}$
• $2 \leq A \leq 6$
• $1 \leq X,Y \leq 10^9$
• 输入均为整数

样例解释 1

可进行的操作有以下两种：

• 支付 $10$ 日元。将 $N$ 替换为 $\displaystyle\left\lfloor\frac{N}{2}\right\rfloor$。
• 支付 $20$ 日元。掷一个等概率出现 $1$ 到 $6$ 的骰子，设掷出的点数为 $b$，将 $N$ 替换为 $\displaystyle\left\lfloor\frac{N}{b}\right\rfloor$。 最优做法是进行前者操作 $2$ 次。

样例解释 2

可进行的操作有以下两种：

• 支付 $20$ 日元。将 $N$ 替换为 $\displaystyle\left\lfloor\frac{N}{2}\right\rfloor$。
• 支付 $20$ 日元。掷一个等概率出现 $1$ 到 $6$ 的骰子，设掷出的点数为 $b$，将 $N$ 替换为 $\displaystyle\left\lfloor\frac{N}{b}\right\rfloor$。 最优的操作如下：
• 首先进行后者操作掷骰子。
• 如果掷出 $4$ 及以上，则 $N=0$。
• 如果掷出 $2$ 或 $3$，则 $N=1$，继续进行前者操作即可使 $N=0$。
• 如果掷出 $1$，则从头再来。

由 ChatGPT 4.1 翻译