10056 - What is the Probability ?

Probability has always been an integrated part of computer algorithms. Where the deterministic algorithms have failed to solve a problem in short time, probabilistic algorithms have come to the rescue. In this problem we are not dealing with any probabilistic algorithm. We will just try to determine the winning probability of a certain player.

A game is played by throwing a dice like thing (it should not be assumed that it has six sides like an ordinary dice). If a certain event occurs when a player throws the dice (such as getting a 3, getting green side on top or whatever) he is declared the winner. There can be N such player. So the first player will throw the dice, then the second and at last the N th player and again the first player and so on. When a player gets the desired event he or she is declared winner and playing stops. You will have to determine the winning probability of one (The I th) of these players.

Input

Input will contain an integer S (S<=1000) at first, which indicates how many sets of inputs are there. The next S lines will contain S sets of inputs. Each line contain an integer N (N<=1000) which denotes the number players, a floating point number p which indicates the probability of the happening of a successful event in a single throw (If success means getting 3 then p is the probability of getting 3 in a single throw. For a normal dice the probability of getting 3 is 1/6), and I (I<=N) the serial of the player whose winning probability is to be determined (Serial no varies from 1 to N). You can assume that no invalid probability (p) value will be given as input.

Output

For each set of input, output in a single line the probability of the I th player to win. The output floating point number will always have four digits after the decimal point as shown in the sample output.

Sample Input:

2
2 0.166666 1
2 0.166666 2

Sample Output:

0.5455
0.4545

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=997

---

這題需要用到一點數學。首先，我們先來了解一下題目的意思，這就是一個有關機率的遊戲，題目會告訴你有幾個玩家，勝率多少，然後要你求出第x個玩家獲勝的機率。那玩家play的順序是從第一個到最後一個，若沒有人獲勝，就到第二輪，若第二輪還沒有人獲勝，就到第三輪，直到有人獲勝為止。

算法大致上就是先求出第一輪x玩家獲勝的機率，再加上第二輪x玩家獲勝的機率...一直加到無窮大。我們先把算式列出來:

設p = 獲勝的機率, q = 沒有獲勝的機率 = 1 - p, n = 總共的玩家數, x = 第幾個玩家要贏

算式就是這樣:

p * q ^ (x - 1) + p * q ^ (n + x - 1) + p * q ^ (2 * n + x - 1)...

接下來我們可以把 p * q ^ (x - 1)提出來:

( p * q ^ (x - 1) ) * ( 1 + q ^ n + q ^ (2 * n)... )

1 + q ^ n + q ^ (2 * n)...很明顯是個無窮等比級數，所以利用無窮等比級數公式代掉後，會變成以下式子:

( p * q ^ (x - 1) ) * ( 1 / (1 - q ^ n) )

整理一下:

( p * q ^ (x - 1) ) / (1 - q ^ n)

這就是最後的公式，只要把input代進去就可以求出解了。

以下是c++程式碼:

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
    int caseNum;

    cin >> caseNum;
    while (caseNum--) {
        int n, x;
        double p, q, ans;

        cin >> n >> p >> x;
        q = 1 - p;
        if (q == 1)
            cout << "0.0000" << endl;
        else {
            ans = pow(q, x - 1) * p / (1 - pow(q, n));
            cout << fixed << setprecision(4) << ans << endl;
        }
    }
    return 0;
}