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 \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 翻译