Cod sursa(job #2209986)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 5 iunie 2018 13:11:59
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAXN = 50;

char mat[MAXN + 1][MAXN + 1];
int sp[MAXN + 1][MAXN + 1];

inline int get(int l1, int c1, int l2, int c2) {
    if(l1 > l2 || c1 > c2)
        return 0;
    return sp[l2][c2] - sp[l1 - 1][c2] - sp[l2][c1 - 1] + sp[l1 - 1][c1 - 1];
}

inline ll gcd(ll a, ll b) {
    ll r;
    while(b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    FILE *fi, *fout;
    int t, i, j, n, m;
    fi = fopen("boundingbox.in" ,"r");
    fout = fopen("boundingbox.out" ,"w");
    fscanf(fi,"%d " ,&t);
    while(t > 0) {
        t--;
        fscanf(fi,"%d %d " ,&n,&m);
        for(i = 1; i <= n; i++) {
            fscanf(fi,"%s " ,mat[i] + 1);
            for(j = 1; j <= m; j++) {
                mat[i][j] -= '0';
                sp[i][j] = sp[i - 1][j] + sp[i][j - 1] + mat[i][j] - sp[i - 1][j - 1];
            }
        }
        ll a = 0, b = (1LL << sp[n][m]);
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= m; j++) {
                a += (1LL << get(1, 1, i - 1, m));
                a += (1LL << get(1, 1, n, j - 1));
                a += (1LL << get(1, j + 1, n, m));
                a += (1LL << get(i + 1, 1, n, m));
                a -= (1LL << get(1, 1, i - 1, j - 1));
                a -= (1LL << get(1, j + 1, i - 1, m));
                a -= (1LL << get(i + 1, 1, n, j - 1));
                a -= (1LL << get(i + 1, j + 1, n, m));
                a++;
                //printf("%lld " ,a);
            }
        }
        a = (1LL * n * m * (1LL << sp[n][m])) - a;
        ll aux = gcd(a, b);
        a /= aux;
        b /= aux;
        fprintf(fout,"%lld/%lld\n" ,a,b);
    }
    fclose(fi);
    fclose(fout);
    return 0;
}