← 返回题目列表

AtCoder · abc350_e

H. 向 0

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

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

最优策略如下:

  • 首先,执行第二个操作来掷骰子。
    • 如果结果是 4 或更大,则 N 变为 0.
    • 如果结果是 2 or 3,然后 N 变为 1。现在,执行第一个操作 N = 0.
    • 如果结果是 1,从头开始。

示例输入 3

314159265358979323 4 223606797 173205080

示例输出 3

6418410657.7408381