AT_abc350_e [ABC350E] Toward 0

[problemUrl]: https://atcoder.jp/contests/abc350/tasks/abc350_e 整数 $ 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 $ にするまでに払う必要がある金額の期待値の最小値を求めてください。 なお、サイコロの出目は操作ごとに独立であり、操作の選択はそれまでの操作の結果を確認してから行うことができます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A $ $ X $ $ Y $

答えを出力せよ。 真の解との絶対誤差または相対誤差が $ 10^{-6} $ 以下のとき正解と判定される。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^{18} $ - $ 2\ \leq\ A\ \leq\ 6 $ - $ 1\ \leq\ X,Y\ \leq\ 10^9 $ - 入力は全て整数である ### Sample Explanation 1 行える操作は 次の $ 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 $ 回行うのが最適です。 ### Sample Explanation 2 行える操作は 次の $ 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 $ が出た場合最初からやり直します。