No.425 The Winning Strategy for Rock-Paper-Scissors
はむこ
btkProblem Statement
There is a winning strategy for rock-paper-scissors.
Humans have a psychological bias: "after a draw, it is hard to play the same hand as the one in that draw."
Exploiting this, it turns out that "after a draw, playing the hand that loses to the hand of that draw" raises the winning rate.
Kamo-kun and Negi-kun compete in rock-paper-scissors.
Kamo-kun's psychological bias is extremely strong, so after a draw he always plays randomly among the different hands, each with probability 1/2.
Negi-kun knows the winning strategy for rock-paper-scissors.
For example, if a draw occurs with "paper", Kamo-kun will next play only rock or scissors.
If Negi-kun plays rock, which loses to the draw's hand "paper", he will never lose.
However, using the winning strategy every time risks being found out, so Negi-kun uses the winning strategy only with probability $p$.
When he does not use the winning strategy, he plays randomly among all the hands, each with probability 1/3.
Furthermore, Negi-kun is very cautious, so at every draw he changes the probability $p$ using the following rules.
(1) At the first draw, the probability $p$ is set to $p_0$.
(2) At the second or later draw, if he used the winning strategy the previous time, the probability $p$ is set to $p_{prev}-q$ ($p_{prev}$ is the previous probability $p$). If $p$ falls below $0$, $p$ is set to $0$.
(3) At the second or later draw, if he did not use the winning strategy the previous time, the probability $p$ is set to $p_{prev}+q$ ($p_{prev}$ is the previous probability $p$). If $p$ exceeds $1$, $p$ is set to $1$.
Note that for the first hand there is no previous result, so neither the winning strategy nor the psychological bias applies.
That is, both players play randomly among all the hands, each with probability 1/3.
Now, Kamo-kun and Negi-kun play rock-paper-scissors until one game is decided. Find the probability that Negi-kun wins.
Input
$p_0\ q$
$0 \leq p_0 \leq 100$, integer, expressed as a percentage (in %)
$0 \leq q \leq 100$, integer, expressed as a percentage (in %)
Output
Output the probability that Negi-kun wins.
An error of up to $10^{-6}$ is allowed.
Print a newline at the end.
Sample
Sample 1
Input
0 0
Sample Output
0.5
Even if Kamo-kun has the psychological bias, if Negi-kun always plays randomly, the winning rate is 50%.
Sample 2
Input
100 0
Sample Output
0.666666666666
If he always uses the winning strategy without fearing being found out, the winning rate rises to 2/3.
Sample 3
Input
100 100
Sample Output
0.6
If he alternates between using and not using the winning strategy, he wins with 60%.
The rock-paper-scissors proceeds as follows.
In the 1st game, both play all the hands with probability 1/3, so Negi-kun wins with probability 1/3. If it is a draw, proceed to the next game.
In the 2nd game, since this is the first draw, by rule (1) Negi-kun uses the winning strategy with probability $p=p_0=1$. Therefore Negi-kun wins with probability 1/2. If it is a draw, proceed to the next game.
In the 3rd game, since the draw occurred with the winning strategy used the previous time, by rule (2) Negi-kun uses the winning strategy with probability $p=p_{prev}-q=0$. Therefore Negi-kun wins with probability 1/3. If it is a draw, proceed to the next game.
In the 4th game, since the draw occurred without the winning strategy used the previous time, by rule (3) Negi-kun uses the winning strategy with probability $p=p_{prev}+q=1$. Therefore Negi-kun wins with probability 1/2. If it is a draw, proceed to the next game.
In the 5th game, since the draw occurred with the winning strategy used the previous time, by rule (2) Negi-kun uses the winning strategy with probability $p=p_{prev}-q=0$. Therefore Negi-kun wins with probability 1/3. If it is a draw, proceed to the next game.
This repeats thereafter.
Sample 4
Input
20 80
Sample Output
0.548148148148148
Sample 5
Input
3 14
Sample Output
0.51149191514
An error of up to $10^{-6}$ is allowed in the output.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。