Pagini recente » Cod sursa (job #3291776) | Cod sursa (job #2913845) | Cod sursa (job #2308709) | Cod sursa (job #1712087) | Cod sursa (job #2085303)
#include <bits/stdc++.h>
using namespace std;
ifstream in("minesweeper.in");
ofstream out("minesweeper.out");
const int DIM = 500;
const long double EPS = 0.0;
valarray<long double> sys[DIM];
int aux[DIM][DIM]; long double ans[DIM];
inline int id(int x, int y)
{
return aux[x][y];
}
bool zero(long double x)
{
return fabs(x) <= EPS;
}
int main(void)
{
int n, m, h = 0;
in >> n >> m; n *= m;
for (int i = 0; i <= n; ++i)
for (int j = 0; i + j <= n; ++j)
aux[i][j] = ++h;
for (int i = 0; i <= n; ++i)
for (int j = 0; i + j <= n; ++j)
sys[id(i, j)].resize(h + 3);
for (int i = 0; i <= n; ++i) {
for (int j = 0, k = n - i - j; i + j <= n; ++j, --k) {
sys[id(i, j)][id(i, j)] = 1;
if (i == 0 and j == 0)
continue;
sys[id(i, j)][h + 1] = 1;
if (i) sys[id(i, j)][id(i - 1, j + 1)] -= 1.0 * i / n;
if (j) sys[id(i, j)][id( i , j - 1)] -= 1.0 * j / n;
if (k) sys[id(i, j)][id(i + 1, j )] -= 1.0 * k / n;
} }
for (int i = 1, j = 1; i <= h and j <= h; ++j) {
bool ok = false; long double val;
for (int k = i; k <= h and !ok; ++k) {
if (zero(sys[k][j]))
continue;
ok = true;
if (k != i)
swap(sys[i], sys[k]);
}
if (!ok)
continue;
val = sys[i][j]; sys[i] /= val;
for (int k = i + 1; k <= h; ++k) {
if (zero(sys[k][j]))
continue;
val = sys[k][j];
sys[k] -= val * sys[i];
}
++i;
}
for (int i = h; i >= 1; --i) {
for (int j = 1; j <= h; ++j) {
if (zero(sys[i][j]))
continue;
ans[j] = sys[i][h + 1];
for (int k = j + 1; k <= h; ++k)
ans[j] -= ans[k] * sys[i][k];
ans[j] /= sys[i][j];
break;
} }
out << setprecision(10) << fixed << ans[id(n, 0)] << endl;
return 0;
}