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}$，则视为正确。

3 2 10 20

20.000000000000000

3 2 20 20

32.000000000000000

314159265358979323 4 223606797 173205080

6418410657.7408381

提示

$1 \leq N \leq 10^{18}$ $2 \leq A \leq 6$ $1 \leq X, Y \leq 10^9$ 所有输入值均为整数。可用的操作如下：

支付 $10$ 日元。将 $N$ 替换为 $\displaystyle\left\lfloor\frac{N}{2}\right\rfloor$。 支付 $20$ 日元。掷骰子。设掷得的点数为 $b$，并将 $N$ 替换为 $\displaystyle\left\lfloor\frac{N}{b}\right\rfloor$。

最优策略是执行第一次操作两次。
可用的操作如下：

支付 $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$，则从头开始。

标签: AtCoder|abc350E

来源

AtCoder|abc350E