1571. What is the probability?
Probability is
often an integral part of computer algorithms. When deterministic algorithms
are unable to solve a problem within a reasonable amount of time, probabilistic
algorithms come to the rescue. However, in this problem you are not required to
design a probabilistic algorithm – you only need to compute the probability that a particular
player wins the game.
The game
involves n players who take turns throwing
an object similar to a die (the number of faces is not necessarily six). The
players move in order: first the first player, then the second, and so on up to
the n-th player. If
in a given round none of the players wins, the game continues again starting
from the first player.
A player wins
if, during their turn, a certain event occurs (for example, the number 3 is rolled, a
green face appears, and so on), after which the game ends immediately. The
probability that this winning event occurs in a single throw is p.
Determine the
probability that the player with number i wins.
Input. The first line contains a single integer t (t ≤ 1000) – the number of test
cases. Each of the following lines contains three values: the number
of players n (n ≤ 1000), a real number p (0 ≤ p ≤
1) – the probability of the winning event in a single throw, and the player
number i (1 ≤ i ≤ n) for which the winning probability should be
computed.
Output. For each test case, print
the probability that the i-th player wins. The
answer should be printed with exactly 4 digits after the decimal point.
|
Sample
input |
Sample
output |
|
2 2 0.166666 1 2 0.166666 2 |
0.5455 0.4545 |
SOLUTION
probability
Algorithm analysis
Let us consider
the game from the perspective of probability theory:
·
Each throw is independent of the others;
·
The probability of winning on a single throw is p;
·
The probability of failure on a single throw is 1 – p;
·
The players take turns in a cycle: 1, 2, …, n, 1, 2, … ;
·
The game ends immediately as soon as someone wins.
We are
interested in the probability that the i-th player wins.
The fact that
the i-th player wins
means that:
·
no one has won before his winning throw;
·
the winning event occurs on his turn.
Moreover, the i-th player may
win:
·
on his first throw;
·
on his second throw;
·
on his third throw;
·
and so on.
The final
probability is equal to the sum of the probabilities of all these cases.
For the i-th player to
win on his first turn, two
conditions must be satisfied:
·
The first i – 1 players do not
win. The probability of this event is (1 – p)i – 1.
·
The i-th player wins. The probability of this event is p.
Since the events
are independent, the probability that the i-th player wins on his first turn is
equal to
p ∙ (1 – p)i
– 1
The i-th player
wins on his second turn if:
·
All n players make one throw each and lose: 
·
The first i – 1 players lose again in the second
round. The probability of this event is (1 – p)i
– 1.
·
The i-th player wins. The probability of this event is p.
The probability that the i-th
player wins on his second turn is equal to
p ∙ (1 – p)i
– 1 ∙
(1 – p)n
By reasoning in the same
way, we obtain that the probability for the i-th player to win on his k-th turn is equal to
p ∙ (1 – p)i
– 1 ∙
(1 – p)n(k – 1)
Now it remains to sum the
obtained probabilities. The overall probability that the i-th player wins is equal
to
p ∙ (1 – p)i-1 (1 + (1 – p)n
+ (1 – p)2n + .. + (1 – p)kn + …)
The expression in
parentheses is an infinite geometric progression with first term equal to 1 and common ratio (1 – p)n. The winning probability is
equal to
p ∙ (1 – p)i-1 
= 
It should be noted
separately that when p = 0, the answer is 0.
Algorithm implementation
Read the input data.
scanf("%d",&t);
while(t--)
{
scanf("%d %lf
%d",&n,&p,&i);
If the probability p is equal to 0, print 0.
if (p == 0)
printf("0\n");
else
{
Otherwise, compute the required probability using the
formula given above. Print the result with 4 digits after the decimal point.
res = p * pow(1 - p,i - 1) / (1 - pow(1 - p,n));
printf("%.4lf\n",res);
}
}