問題一覧 > 通常問題

No.1305 Speak of the Devil

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-3}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 149
作問者 : ミドリムシ+ミドリムシ+ / テスター : leafirbyleafirby
12 ProblemId : 3985 / 出題時の順位表
問題文最終更新日: 2020-11-15 16:15:51

問題文

あなたは自身の家で友達と談話をしています。
あなたは今、兄の太郎君をこの談話の場に呼びたいと思いました。

太郎君は現在会社に出勤中ですが、あなたは次の2つの行動のどちらかを選び実行することで太郎君を家に呼び出す事ができます。
・噂をする。太郎君は $1$ 分後に確率 $1/p$ で家に来るが、確率 $(p-1)/p$ で家に来ない。家に来なかった場合、再度2つの行動のどちらかを選び実行する。
・太郎君に電話をして呼び出す。太郎君は $q$ 分後に必ず家に来る。ただし、$q$ 分経つより前に家に来ることはない。

あなたが行動を適切に選び実行した時、太郎君が家に来るまでの時間の期待値の最小値は何分でしょう?

入力

$p$ と $q$ が1行に空白区切りで与えられます。これらは $1$ 以上 $10^9$ 以下の整数です。

出力

太郎君が家に来るまでの時間の期待値の最小値が $s$ 分のとき、$s$ を出力し、最後に改行しなさい。
出力された値と正答との絶対誤差または相対誤差が $10^{-3}$ 以下の場合、ACとします。

サンプル

サンプル1
入力
2 1
出力
1.0000000000

噂をする場合、$1$ 分後に確率 $1/2$ で太郎君が家に来ます。
太郎君に電話をして呼び出す場合、$1$ 分後に確率 $1$ で太郎君が家に来ます。
太郎君を家に早く呼び出すためには、明らかに後者を選ぶべきです。この時、太郎君は $1$ 分後に家に来ます。

サンプル2
入力
1 2
出力
1.0000000000

噂をする場合、$1$ 分後に確率 $1$ で太郎君が家に来ます。
電話をして呼び出す場合、$2$ 分後に確率 $1$ で太郎君が家に来ます。
太郎君を家に早く呼び出すためには、明らかに前者を選ぶべきです。この時、太郎君は $1$ 分後に家に来ます。

サンプル3
入力
2 100
出力
2.0000000000

太郎君が家に来るまで噂をし続けるのが最適です。
この時、期待値は $\displaystyle \sum_{k=1}^\infty(k/2^k)=2$ 分になります。

サンプル4
入力
9 6
出力
6.0000000000

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