No.3318 客に卵をかける
タグ : / 解いたユーザー数 10
作問者 :
Andrew8128
/ テスター :
高橋ゆに
DeltaStruct
kazuppa
elphe
のらら
こめだわら
みうね
seekworser
問題文
岩井星人さんはこれから最大 $N$ 日間お好み焼き屋さんでバイトをする予定です。
最初、お好み焼きを焼く実力は $X$、所持金は $0$ 円です。
1日ごとに以下の2つの選択肢から行動を選びます。
- 研修を受ける： 実力が $Y$ 上昇し、研修期間の日給として $P$ 円を得る。
-
通常業務を行う：
日給として $Q$ 円を得る。ただし確率 $ \frac{1}{\text{実力}} $ で客に卵をかけてしまう。
卵をかけてしまった場合は次のいずれかを選ぶ。
- $R$ 円払い、レモンサワーを客にサービスして事実をもみ消す（このとき、所持金は負の値になってもよい）。
- もみ消さず、店長にばれて即日クビになる。
$N$ 日経過するか、クビになった時点でバイトは終了します。
岩井星人さんはバイトが終了した時点での所持金の期待値を最大化するように行動を選びます。
バイト終了時の所持金の期待値を求めてください。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
入力はすべて整数で与えられる
$1 \leq T \leq 300$
$1 \leq N \leq 10^{12}$
$1 \leq X, Y \leq 100$
$1 \leq P \leq Q \leq 10^5$
$1 \leq R \leq 10^5$
入力
入力は以下の形式で標準入力から与えられる。ここで $\mathrm{case}_i$ は $i$ 番目のテストケースを意味する。
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各テストケースは以下の形式で与えられる。
$N$ $X\ Y$ $P\ Q\ R$
出力
$T$ 行出力してください。
$i$ 行目には $i$ 番目のテストケースについて、バイト終了時点での所持金の期待値を出力してください。
相対誤差 $10^{-8}$ 以内で正解と判定されます。
サンプル
サンプル
入力
5 1 1 1 1 2 10000 2 3 1 1 2 10000 2 3 1 1 2 1 3000 1 1 800 1000 200 1000000000000 100 100 100000 100000 100000
出力
2.0000000000 3.3333333333 3.6666666667 2978490.9090909091 100000000000000000.0000000000
1 つ目のテストケースでは、岩井星人さんの実力は$1$なので、通常業務を行うと100%の確率で卵をかけてしまいますが、通常業務を行い、客に卵をかけてクビになるのが最適です。
2 つ目のテストケースでは、1日目、2日目ともに通常業務を行うのが最適です。
1日目、客に卵をかけない確率が $ \frac{2}{3} $ で、この時岩井星人さんの最終的な所持金は $4$ 円です。
また、1日目、客に卵をかける確率が $ \frac{1}{3} $ で、この時岩井星人さんはもみ消さずにクビになるのが最適で、最終的な所持金は $2$ 円です。
よって答えは、$ \frac{2}{3} \times 4 + \frac{1}{3} \times 2 = \frac{10}{3} $ です。
3 つ目のテストケースでは、1日目、2日目ともに通常業務を行うのが最適です。
1日目、客に卵をかけない確率が $ \frac{2}{3} $ で、この時岩井星人さんの最終的な所持金は $4$ 円です。
また、1日目、客に卵をかける確率が $ \frac{1}{3} $ で、この時岩井星人さんは $1$ 円払ってもみ消すのが最適で、最終的な所持金は $3$ 円です。
よって答えは、$ \frac{2}{3} \times 4 + \frac{1}{3} \times 3 = \frac{11}{3} $ です。
このテストケースがそうであるように、テストケースにおける $N$ の総和は $10^{12}$ 以下とは限らないことに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。