Cod sursa(job #638025)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 20 noiembrie 2011 18:14:58
Problema Minesweeper Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 1.17 kb
#include <cstdio>
#include <cmath>

const int LIM = 100;

int n, m;

double comb[LIM*3][LIM*3];
double dp[LIM][30];

int main()
{
	freopen("minesweeper.in", "r", stdin);
	freopen("minesweeper.out", "w", stdout);
	
	scanf("%d%d", &n, &m);

	comb[0][0] = 1;
	for (int i = 1; i < LIM*3; ++i)
	{
		comb[i][0] = 1;
		for (int j = 1; j <= i; ++j)
			comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
	}
	
	dp[0][0] = 1;
	for (int i = 1; i < LIM; ++i)
	{
		dp[i][1] = 1;
		dp[i][0] = 0;
		for (int j = 2; j <= i && j < 30; ++j)
		{
			dp[i][j] = 0;
			for (int k = 1; k <= i-j+1; ++k)
				dp[i][j] += comb[3*i][3*k] * dp[i-k][j-1];
		}
	}

	fprintf(stderr, "comb(7, 3): %lf\n", comb[7][3]);
	fprintf(stderr, "dp(3, 3): %lf\n", dp[3][3]);
	
	double p = n*m;
	double q = 1/p;
	double E = 0;
	for (int k=0;k<LIM;++k)
	{
		double pk = (2*p + 3*k) * pow(q, 2*p+3*k);
		double sum = 0;
		for (int i = 0; i <= n*m && i <= k; ++i)
			sum += comb[n*m][i] * dp[k][i];
		pk *= sum;
		fprintf(stderr, "%lf\n", pk);
		E += pk;
	}
	
	double fact = 1;
	for (int i = 2; i<= 2*n*m; ++i)
		fact *= i;
		
	E *= fact * pow(0.5, p);
	
	printf("%lf\n", E);
	return 0;
}