ACM 10056 What is the Probability ?

機率好難……
一開始的想法很單純，答案就是題目給的浮點數。
後來想想發現，第i個人擲骰，i未必為1，
而也未必在第一輪就骰出。
所以我想的太簡單了 -.-。
所以正確的思考方式應該為：
n個人中第k個人骰贏得機率是多少？
此人可能在第一輪骰贏、第二輪骰贏、第三輪骰贏……一直到他骰贏的那輪為止。
假設骰贏的機率為p，沒骰贏的機率為q = p - 1
第k個人要骰贏，前面k-1個人一定不會骰贏：
q ^ (k-1)
此人自己需骰贏：
q ^ (k-1) * p
如果他沒骰贏，遊戲被迫進入第二輪，
即第一輪大家都沒骰贏：
q ^ n
第二輪中他骰贏的情況（第一輪沒人贏，第二輪他贏）：
(q ^ n) * q ^ (k-1) * p
第三輪中他骰贏的情況（前二輪沒人贏，第三輪他贏）：
(q ^ 2n) * q ^ (k-1) * p
類推，到第x+1輪他骰贏的情況（前x輪沒人贏，第x+1輪他贏）：
(q ^ xn) * q ^ (k-1) * p
所以若要計算他所有骰贏的可能情況，
就是第一輪骰贏的機率 + 第二輪骰贏的機率 + ... + 第x輪骰贏的機率：
q ^ (k-1) * p + (q ^ n) * q ^ (k-1) * p + (q ^ 2n) * q ^ (k-1) * p + ... + (q ^ xn) * q ^ (k-1) * p
以下化簡原式：

1. q ^ (k-1) * p [1 + (q ^ n) + (q ^ 2n) + ... + (q ^ xn)] (取出q ^ (k-1)*p)
   
2. 1 + (q ^ n) + (q ^ 2n) + ... + (q ^ xn) 是無窮等比級數（根本就不知道他哪一輪會贏）
   

公比為q ^ n。
所以2.式可以化簡為1 / (1 - q ^ n)（查詢等比級數公式/無窮等比級數公式）
原式化簡為：
[q ^ (k-1) * p] / (1 - q ^ n)。
另外要注意，當p為0時，此公式分母為0，所以輸出需另外處理。
（就是輸出0.0000而已啦）

/* ACM 10056
 * mythnc
 * 2011/10/13 11:47:52   
 * run time: 0.008
 */
#include <stdio.h>
#include <math.h>

int main(void)
{
    int set, n, k;  /* n players, the kth player */
    double p;

    scanf("%d", &set);
    while (set-- > 0) {
        scanf("%d %lf %d", &n, &p, &k);
        if (p == 0.0) {
            printf("0.0000\n");
            continue;
        }
        if (k == 1)
            printf("%.4f\n", p / (1 - pow(1-p, n)));
        else
            printf("%.4f\n", p * pow(1-p, k-1) / (1 - pow(1-p, n)));
    }
    return 0;
}