变为 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}$ 时,视为正确。

样例

3 2 10 20

20.000000000000000

可用的操作如下:

• 支付 $10$ 日元,将 $N$ 替换为 $\displaystyle\left\lfloor\frac{N}{2}\right\rfloor$。
• 支付 $20$ 日元,掷一次骰子,设结果为 $b$,将 $N$ 替换为 $\displaystyle\left\lfloor\frac{N}{b}\right\rfloor$。

最优策略是进行两次第一种操作。

3 2 20 20

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$ 或 $3$,则 $N$ 变为 $1$。此时进行第一种操作,使 $N = 0$。
• 如果结果为 $1$,则从头重新开始。

314159265358979323 4 223606797 173205080

6418410657.7408381

数据范围

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