2015年2月3日 星期二

2015 Facebook Hacker Cup, Round 2, problem: (B) All Critical

#include <iostream>
#include <cstdio>

using namespace std;

int T;
double DP[30];

double C(int m, int n)
{
    n = min(n, m-n);

    double re = 1;

    for(int ni = 1; ni <= n; ni++)
    {
        re *= m-ni+1;
        re /= ni;
    }

    return re;
}

double pwd(double x, int n)
{
    if( n == 0 ) return 1;

    double p = pwd(x, n/2);

    if( n&1 ) return p*p*x;
    else return p*p;
}

int main()
{

    scanf("%d", &T);

    for(int Ti = 1; Ti <= T; Ti++)
    {
        double p;
        scanf("%lf", &p);

        DP[20] = 0;

        for(int i = 19; i >= 0; i--)
        {
            double tmp = 1;

            for(int j = 1; j+i <= 20; j++)
            {
                tmp += DP[i+j]*pwd(p, j)*pwd(1-p, 20-i-j)*C(20-i, j);
            }

            DP[i] = tmp/(1-pwd(1-p, 20-i) );
        }

        printf("Case #%d: ", Ti);
        printf("%.6f\n", DP[0]);
    }
}

沒有留言:

張貼留言