2014年9月19日 星期五

2014/9/19 codevs 1060 搞笑世界杯

// http://codevs.cn/problem/1060/
#include <iostream>
#include <cstdio>

using namespace std;

int N;
double DP[2500][2500];

int main()
{
    scanf("%d", &N);
    N/=2;

    DP[2][0] = DP[0][2] = 1; DP[1][1] = 0;

    for(int Ni = 3; Ni <= N*2; Ni++)
    {
        DP[Ni][0] = DP[0][Ni] = 1;

        for(int Nj = 1; Nj < Ni; Nj++)
        {
            DP[Ni-Nj][Nj] = 0.5*DP[Ni-Nj-1][Nj]+0.5*DP[Ni-Nj][Nj-1];
        }
    }

    printf("%.4lf\n", DP[N][N]);
}

沒有留言:

張貼留言