Cod sursa(job #2215932)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 24 iunie 2018 12:39:59
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>
#define MAXN 50

int v[1 + MAXN][1 + MAXN];
int s[1 + MAXN][1 + MAXN];
int main(){
    FILE*fi,*fo;
    fi = fopen("boundingbox.in","r");
    fo = fopen("boundingbox.out","w");

    int t;
    fscanf(fi,"%d", &t);
    for(int z = 1; z <= t; z++){
        int n, m;
        fscanf(fi,"%d%d", &n, &m);
        for(int i = 1; i <= n; i++){
            fgetc(fi);
            for(int j = 1; j <= m; j++){
                v[i][j] = fgetc(fi) - '0';
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v[i][j];
            }
        }
        if(s[n][m] == 0)
            fprintf(fo,"0/1\n");
        else{
            long long ans = (n * m) * ((1LL << s[n][m]) - 1);
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++){
                    ans -= (1LL << (s[n][m] - s[n][j])) - 1;
                    ans -= (1LL << s[n][j - 1]) - 1;
                    ans -= (1LL << (s[n][m] - s[i][m])) - 1;
                    ans -= (1LL << s[i - 1][m]) - 1;

                    ans += (1LL << s[i - 1][j - 1]) - 1;
                    ans += (1LL << (s[i - 1][m] - s[i - 1][j])) - 1;
                    ans += (1LL << (s[n][j - 1] - s[i][j - 1])) - 1;
                    ans += (1LL << (s[n][m] - s[i][m] - s[n][j] + s[i][j])) - 1;
                }
            printf("%lld\n", ans);
            long long a = ans, b = (1LL << s[n][m]), r;
            while(b){
                r = a % b;
                a = b;
                b = r;
            }
            fprintf(fo,"%lld/%lld\n", ans / a, (1LL << s[n][m]) / a);
        }
    }

    return 0;
}