Cod sursa(job #2085300)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 9 decembrie 2017 21:54:50
Problema Minesweeper Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in("minesweeper.in");
ofstream out("minesweeper.out");

const int DIM = 500;
const long double EPS = 1e-7;

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 -EPS < x and 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; 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;
}