Cod sursa(job #2215932)

Utilizator Data 24 iunie 2018 12:39:59 Boundingbox 100 cpp done Arhiva de probleme 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;
}
``````