E - Toward 0 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 450 点

問題文

整数 N が与えられます。あなたは次の 2 種類の操作を行うことができます。

  • 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

行える操作は 次の 2 種類です。

  • 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

3 2 20 20

出力例 2

32.000000000000000

行える操作は 次の 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 が出た場合最初からやり直します。

入力例 3

314159265358979323 4 223606797 173205080

出力例 3

6418410657.7408381

Score: 450 points

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 4 or greater, then N becomes 0.
    • If the outcome is 2 or 3, 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