問題一覧 > 通常問題

No.23 技の選択

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-2}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 264
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
5 ProblemId : 33 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:02

問題文

体力の初期値がHの敵を倒したい。
敵は体力が0以下になると倒せる。
攻撃方法は通常攻撃と必殺技の2通りがある。
通常攻撃は1回の攻撃でAのダメージを与える。
通常攻撃はかならず当たる。
必殺技は1回の攻撃でDのダメージを与える。
ただし、必殺技が当たる確率は2/3である。
必殺技は1/3の確率でダメージは0である。
最終的に敵を倒すまでの回数の期待値を
最小にするように攻撃を選んでいく。
敵を倒すまでの攻撃数の期待値はいくつか?

入力

H A D

一行に、敵の体力Hと通常攻撃のダメージ量A、必殺技のダメージ量Dが半角スペース区切りで与えられる。
$1 \le H,A,D \le 10000 $

出力

答えを小数で出力してください。なお、誤差は絶対誤差・相対誤差0.01の範囲までは許容する。

サンプル

サンプル1
入力
10 10 20
出力
1

通常攻撃1回で確実に敵を倒せる。

サンプル2
入力
38 10 14
出力
4

必殺技を使わず通常攻撃4回で倒せる。
最短では必殺技3回でも倒せるが、命中率が2/3のため、必殺技を使うだけの攻撃では期待値は4.5回になってしまう。
0回通常攻撃をし、残りHP38から必殺技のみの期待値は4.5回である。(合計4.5回)
1回通常攻撃をし、残りHP28から必殺技のみの期待値は3回である。(合計4回)
2回通常攻撃をし、残りHP18から必殺技のみでも期待値は3回である。(合計5回)
3回通常攻撃をし、残りHP8から必殺技のみでも期待値は1.5回である。(合計4.5回)
この時、最も期待値最小は4回である。

サンプル3
入力
49 7 17
出力
4.5

通常攻撃も必殺技も使って期待値4.5回で倒せる。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。