103504: [Atcoder]ABC350 E - Toward 0

Problem Statement

You are given an integer $N$. You can perform the following two types of operations:

• Pay $X$ yen to replace $N$ with $\displaystyle\left\lfloor\frac{N}{A}\right\rfloor$.
• Pay $Y$ yen to roll a die (dice) that shows an integer between $1$ and $6$, inclusive, with equal probability. Let $b$ be the outcome of the die, and replace $N$ with $\displaystyle\left\lfloor\frac{N}{b}\right\rfloor$.

Here, $\lfloor s \rfloor$ denotes the greatest integer less than or equal to $s$. For example, $\lfloor 3 \rfloor=3$ and $\lfloor 2.5 \rfloor=2$.

Determine the minimum expected cost paid before $N$ becomes $0$ when optimally choosing operations.
The outcome of the die in each operation is independent of other rolls, and the choice of operation can be made after observing the results of the previous operations.

Constraints

• $1 \leq N \leq 10^{18}$
• $2 \leq A \leq 6$
• $1 \leq X, Y \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.
Your output will be considered correct if the absolute or relative error from the true answer is at most $10^{-6}$.

Sample Input 1

3 2 10 20

Sample Output 1

20.000000000000000

The available operations are as follows:

• Pay $10$ yen. Replace $N$ with $\displaystyle\left\lfloor\frac{N}{2}\right\rfloor$.
• Pay $20$ yen. Roll a die. Let $b$ be the outcome, and replace $N$ with $\displaystyle\left\lfloor\frac{N}{b}\right\rfloor$.

The optimal strategy is to perform the first operation twice.

Sample Input 2

3 2 20 20

Sample Output 2

32.000000000000000

The available operations are as follows:

• Pay $20$ yen. Replace $N$ with $\displaystyle\left\lfloor\frac{N}{2}\right\rfloor$.
• Pay $20$ yen. Roll a die. Let $b$ be the outcome, and replace $N$ with $\displaystyle\left\lfloor\frac{N}{b}\right\rfloor$.

The optimal strategy is as follows:

• First, perform the second operation to roll the die.
  • If the outcome is $3$ or greater, then $N$ becomes $0$.
  • If the outcome is $2$, then $N$ becomes $1$. Now, perform the first operation to make $N = 0$.
  • If the outcome is $1$, restart from the beginning.

Sample Input 3

314159265358979323 4 223606797 173205080

Sample Output 3

6418410657.7408381

问题描述

给你一个整数 $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$。

最优策略如下：

• 首先执行第二次操作，掷骰子：
  • 如果结果是 $3$ 或更大，那么 $N$ 变为 $0$。
  • 如果结果是 $2$，那么 $N$ 变为 $1$。现在执行第一次操作，使 $N = 0$。
  • 如果结果是 $1$，则从头开始。

样例输入3

314159265358979323 4 223606797 173205080

样例输出3

6418410657.7408381