問題文
わりとねこくんは、ねこ星で大流行中のゲーム「ニャオメタリーダッシュ」で遊んでいます。
ニャオメタリーダッシュのステージは 個の区間 に分かれており、最初、区間 の難易度は です。 わりとねこくんが難易度 の区間を 回プレイすると、成功率 (すなわち確率 )で成功して次の区間へ進み、失敗率 (確率 )で失敗します。
わりとねこくんは、ステージに挑戦する前に最大 回まで練習をすることができます。 回の練習では任意の つの区間を選び、その区間の難易度を だけ減少させることができます。ただし、すでに難易度が である区間を選んだ場合、難易度は のまま変わりません。
ステージへの挑戦は区間 から始まり、区間 をこの順番に連続で成功するとクリアとなります。途中で失敗した場合は、即座に区間 に戻されて再び区間 からやり直しになります。 また、成功・失敗にかかわらず、区間を つプレイするごとに 単位時間がかかります。
適切に練習を行ったときに、ステージをクリアするまでにかかる時間の期待値の最小値を求めてください。 ここで、答えは 以下であることが保証されています。
制約
- ()
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
出力
クリアまでにかかる時間の期待値の最小値を出力してください。 なお、出力された値と真の値との絶対誤差または相対誤差が 以下であれば正解とみなされます。
入力例 1
2 100
500 600
出力例 1
6.0000000000
区間 に対して練習を 回行うと、区間の難易度はそれぞれ (どちらも成功率 )になります。 このとき、クリアまでにかかる時間の期待値はちょうど となり、これが最小です。
入力例 2
3 0
200 500 750
出力例 2
22.0000000000
練習を行うことができず、それぞれの区間の成功率は となります。 区間 までを突破する期待時間は 、区間 までは 、区間 まで(クリア)は となります。
入力例 3
2 500
500 500
出力例 3
2.9610124003
区間 を 回、区間 を 回練習して難易度をそれぞれ にしたとき、期待値は となり、これが最小です。
誤差ジャッジ:絶対誤差または相対誤差が10-6以下なら正解です。
参加受付は終了しました。
ログインして解答を提出
解答の提出や採点結果の確認には、ログインが必要です。
ログインする