Cod sursa(job #1822510)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 5 decembrie 2016 00:45:10
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>
using namespace std;
typedef long double f80;

const int SPQR = 23 * 23 + 5;
const f80 EPS = 1e-18L;

int n, m;

valarray<f80> gs[SPQR];
int cod[23][23];

inline bool eq(const f80 &a, const f80 &b) {
    return abs(a - b) < EPS; }

int main(void) {
    ifstream fi("minesweeper.in");
    ofstream fo("minesweeper.out");
    f80 rat;
    int t;

    fi >> n >> t;
    n *= t;

    for (int i = 0; i <= n; ++i)
    for (int j = 0; i + j <= n; ++j)
        cod[i][j] = m++; // I'm a shame...

    for (int i = 0; i <= n; ++i)
    for (int j = 0; i + j <= n; ++j)
        gs[cod[i][j]].resize(m + 1);

    for (int k, i = 0; i <= n; ++i) {
    for (int j = 0; i + j <= n; ++j) {
        if (i == 0 && j == 0) {
            gs[cod[i][j]][cod[i][j]] = 1.0;
            continue; }

        k = n - i - j;

        gs[cod[i][j]][m] = 1.0;
        gs[cod[i][j]][cod[i][j]] = 1.0;

        if (i > 0) gs[cod[i][j]][cod[i - 1][j + 1]] = -f80(i) / f80(n);
        if (j > 0) gs[cod[i][j]][cod[i][j - 1]] = -f80(j) / f80(n);
        if (k > 0) gs[cod[i][j]][cod[i + 1][j]] = -f80(k) / f80(n); } }

    for (int k, i = 0, j = 0; i < m && j < m; ++j) {
        if (eq(gs[i][j], 0.0))  {
            for (k = i; k < m; ++k) if (!eq(gs[k][j], 0.0)) {
                swap(gs[k], gs[i]);
                break; }
            if (k == m)
                continue; }

        for (k = 0; k < m; ++k) if (k != i && !eq(gs[k][j], 0.0))
            gs[k]-= gs[i] * (gs[k][j] / gs[i][j]);
        ++i; }

    fo << setprecision(10) << fixed;
    fo << gs[cod[n][0]][m] / gs[cod[n][0]][cod[n][0]] << '\n';

    return 0; }

// 31447249617.7365264893