Codeforces 518D Ilya and Escalator (概率dp)

Codeforces 518D Ilya and Escalator (概率dp)

Ilya and Escalator time limit per test: 2 seconds memory limit per test: 256 megabytes

Ilya got tired of sports programming, left university and got a job in the subway. He was given the task to determine the escalator load factor.

Let's assume that n people stand in the queue for the escalator. At each second one of the two following possibilities takes place: either the first person in the queue enters the escalator with probability p, or the first person in the queue doesn't move with probability(1?-?p), paralyzed by his fear of escalators and making the whole queue wait behind him.

Formally speaking, the i-th person in the queue cannot enter the escalator until people with indices from1 toi?-?1 inclusive enter it. In one second only one person can enter the escalator. The escalator is infinite, so if a person enters it, he never leaves it, that is he will be standing on the escalator at any following second. Ilya needs to count the expected value of the number of people standing on the escalator aftert seconds.

Your task is to help him solve this complicated task.

Input

The first line of the input contains three numbersn,?p,?t (1?≤?n,?t?≤?2000,0?≤?p?≤?1). Numbers n and t are integers, numberp is real, given with exactly two digits after the decimal point.

Output

Print a single real number — the expected number of people who will be standing on the escalator aftert seconds. The absolute or relative error mustn't exceed10^?-?6.

Sample test(s) Input

1 0.50 1

Output

0.5

Input

1 0.50 4

Output

0.9375

Input

4 0.20 2

Output

0.4

題目鏈接：http://codeforces.com/contest/518/problem/d

題目大意：n個人排隊上電梯，排頭每秒上去的概率為p，一共t秒，求t秒都電梯內人數的期望

題目分析：簡單的概率dp，dp[i][j]表示第i秒電梯上有j個人的概率，最後累計一下期望

#include 
#include 
double dp[2005][2005];

int main()
{
    int n, t;
    double p, ans = 0;
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    scanf("%d %lf %d", &n, &p, &t);
    for(int i = 1; i <= t; i++)
    {
        for(int j = n; j >= 0; j--)
        {
            if(j == n)
                //第i秒有n個人的概率等於第i－1秒有j－1個人的概率乘第i秒第j個人進電梯
                //的概率加上第i - 1秒電梯就已經有n個人的概率
                dp[i][j] = dp[i - 1][j - 1] * p + dp[i - 1][j];
            else if(j != 0)
                //這裡dp[i - 1][j]要乘(1 - p)表示第i秒排頭不進電梯
                dp[i][j] = dp[i - 1][j - 1] * p + dp[i - 1][j] * (1 - p);
            else
                //第i秒電梯裡沒人的概率為第i－1秒電梯裡沒人的概率乘(1 - p)表示
                //第i秒時排頭不進電梯
                dp[i][j] = dp[i - 1][j] * (1 - p);
        }
    }
    for(int i = 1; i <= t; i++)
        ans += (dp[t][i] * i);
    printf("%.7f\n", ans);
}