No.1305 Speak of the Devil
ミドリムシ
leafirbyProblem Statement
You are chatting with friends at your home.
You now want to call your older brother Taro to join this conversation.
Taro is currently at work, but you can get him to come home by choosing and performing one of the following 2 actions.
・Gossip about him. After $1$ minute, Taro comes home with probability $1/p$, and does not come home with probability $(p-1)/p$. If he does not come home, you again choose and perform one of the 2 actions.
・Call Taro on the phone to summon him. Taro always comes home after $q$ minutes. However, he never comes home before $q$ minutes have passed.
When you choose and perform your actions appropriately, what is the minimum expected time, in minutes, until Taro comes home?
Input
$p$ and $q$ are given on one line, separated by a space. They are integers between $1$ and $10^9$, inclusive.
Output
If the minimum expected time until Taro comes home is $s$ minutes, output $s$, followed by a newline.
Your answer is judged as AC if the absolute error or relative error between the output value and the correct answer is at most $10^{-3}$.
Sample
Sample 1
Input
2 1
Output
1.0000000000
If you gossip, Taro comes home after $1$ minute with probability $1/2$.
If you call him on the phone, Taro comes home after $1$ minute with probability $1$.
To get Taro home quickly, you should clearly choose the latter. In this case, Taro comes home after $1$ minute.
Sample 2
Input
1 2
Output
1.0000000000
If you gossip, Taro comes home after $1$ minute with probability $1$.
If you call him on the phone, Taro comes home after $2$ minutes with probability $1$.
To get Taro home quickly, you should clearly choose the former. In this case, Taro comes home after $1$ minute.
Sample 3
Input
2 100
Output
2.0000000000
It is optimal to keep gossiping until Taro comes home.
In this case, the expected value is $\displaystyle \sum_{k=1}^\infty(k/2^k)=2$ minutes.
Sample 4
Input
9 6
Output
6.0000000000
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。