Pagini recente » Cod sursa (job #937987) | Cod sursa (job #1110013) | Cod sursa (job #1954806) | Cod sursa (job #1642253) | Cod sursa (job #677638)
Cod sursa(job #677638)
#include <cstdio>
#include <cstring>
#define StepMax 100000
#define NMax 23
using namespace std;
int N;
double DP[2][NMax][NMax], S;
void Solve ()
{
DP[0][N][0]=1;
for (int Step=1; Step<=StepMax; ++Step)
{
for (int E=0; E<=N; ++E)
{
for (int F=0; F<=N-E; ++F)
{
int Q=N-E-F;
if (Q==N)
{
continue;
}
if (E>0)
{
DP[1][E-1][F+1]+=(1.0*E)/(1.0*N)*DP[0][E][F];
}
if (F>0)
{
DP[1][E][F-1]+=(1.0*F)/(1.0*N)*DP[0][E][F];
}
if (Q>0)
{
DP[1][E+1][F]+=(1.0*Q)/(1.0*N)*DP[0][E][F];
}
}
}
S+=(Step*DP[1][0][0]);
memcpy (DP[0], DP[1], sizeof (DP[0]));
memset (DP[1], 0, sizeof (DP[1]));
}
}
void Read ()
{
freopen("minesweeper.in", "r", stdin);
int M;
scanf("%d%d", &N, &M);
N*=M;
}
void Print ()
{
freopen("minesweeper.out", "w", stdout);
printf ("%.6lf\n", S);
}
int main ()
{
Read ();
Solve ();
Print ();
return 0;
}