Cod sursa(job #1230866)
Utilizator | Data | 19 septembrie 2014 12:32:25 | |
---|---|---|---|
Problema | Boundingbox | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Infoarena Cup 2014 | Marime | 7.42 kb |
#include <cstdio>
#include <cstring>
using namespace std;
int sp1 [55][55], sp2 [55][55], a [51][51], aria [10001], dp [55][55], aux [10001], ans [10001];
char s [55];
int n, m;
long long num = 0;
void read () {
int i, j;
scanf ("%d%d\n", &n, &m);
for (i = 1; i <= n; i ++) {
gets (s + 1);
for (j = 1; j <= m; j ++) {
a [i][j] = s [j] - '0';
sp1 [i][j] = sp1 [i][j - 1] + a [i][j];
sp2 [i][j] = sp2 [i - 1][j] + a [i][j];
if (a [i][j] == 1)
num ++;
}
}
}
void reset () {
memset (sp1, 0, sizeof (sp1));
memset (sp2, 0, sizeof (sp2));
memset (dp, 0, sizeof (dp));
num = 0;
aria [0] = 1;
aria [1] = 0;
}
void adunare (const int &value) {
int i, tr;
aria [1] += value;
tr = aria [1] / 10;
aria [1] = aria [1] % 10;
i = 2;
while (tr) {
aria [i] += tr;
tr = aria [i] / 10;
aria [i] = aria [i] % 10;
i ++;
}
-- i;
if (i > aria [0])
aria [0] = i;
}
void makeDp () {
int i, j;
for (i = 1; i <= n; i ++)
for (j = 1; j <= m; j ++)
dp [i][j] = dp [i - 1][j] + dp [i][j - 1] - dp [i - 1][j - 1] + a [i][j];
}
void impartire (int x [], long long value, int ans []) {
long long d = 0, r = 0;
int i = 1, st, dr, f;
if (value == 0)
return ;
st = 1;
dr = x [0];
while (st < dr) {
f = x [st];
x [st] = x [dr];
x [dr] = f;
st ++; dr --;
}
while (d < value && i <= x [0]) {
d = 1ll * d * 10 + x [i];
i ++;
}
-- i;
ans [0] = 0;
for (; i <= x [0]; i ++) {
ans [++ ans [0]] = d / value;
r = d - 1ll * (1ll * d / value) * value;
if (i + 1 <= x [0])
d = 1ll * r * 10 + x [i + 1];
}
}
long long impartire1 (int x [], long long value) {
long long d = 0, r = 0;
int i = 1, f, st ,dr;
st = 1;
dr = x [0];
while (st < dr) {
f = x [st];
x [st] = x [dr];
x [dr] = f;
st ++; dr --;
}
while (d < value && i <= x [0]) {
d = 1ll * d * 10 + x [i];
i ++;
}
-- i;
if (d < value)
return d;
for (; i <= x [0]; i ++) {
r = d - 1ll * (1ll * d / value) * value;
if (i + 1 <= x [0])
d = 1ll * r * 10 + x [i + 1];
}
return r;
}
long long gcd () {
long long d, c, r;
memcpy (aux, aria, sizeof (aux));
d = impartire1 (aux, num);
c = num;
while (d) {
r = c % d;
c = d;
d = r;
}
return c;
}
void solve () {
int i, j, k, l, l1, l2, l3, l4, h, ll1, ll2, ll3, ll4;
long long g, cmmdc;
adunare (num);
num = (1ll << num);
makeDp ();
for (i = 1; i <= n; i ++)
for (j = 1; j <= m; j ++)
for (k = i; k <= n; k ++)
for (l = j; l <= m; l ++)
if (!(i == k && l == j)) {
l1 = sp1 [i][l] - sp1 [i][j - 1];
l2 = sp1 [k][l] - sp1 [k][j - 1];
l3 = sp2 [k][j] - sp2 [i - 1][j];
l4 = sp2 [k][l] - sp2 [i - 1][l];
g = 1;
if (l1 && l2 && l3 && l4) {
h = (dp [k][l] - dp [i - 1][l] - dp [k][j - 1] + dp [i - 1][j - 1]);
if (i == k || j == l) {
h = h - 2;
g = (1ll << h);
}
else {
ll1 = l1 - a [i][j] - a [i][l];
if (ll1 != 0) {
g = 1ll * g * ll1;
h --;
}
ll2 = l2 - a [k][j] - a [k][l];
if (ll2 != 0) {
g = 1ll * g * ll2;
h --;
}
ll3 = l3 - a [i][j] - a [k][j];
if (ll3 != 0) {
g = 1ll * ll3;
h --;
}
ll4 = l4 - a [i][l] - a [k][l];
if (ll4 != 0) {
g = 1ll * g * ll4;
h --;
}
if (a [i][j]) {
if (ll1 == 0) {
h --;
ll1 = 1;
}
else
if (ll3 == 0) {
h --;
ll3 = 1;
}
}
if (a [i][l]) {
if (ll1 == 0) {
h --;
ll1 = 1;
}
else
if (ll4 == 0) {
h --;
ll4 = 1;
}
}
if (a [k][j]) {
if (ll3 == 0) {
h --;
ll3 = 1;
}
else
if (ll2 == 0) {
h --;
ll2 = 1;
}
}
if (a [k][l]) {
if (ll2 == 0) {
h --;
ll2 = 1;
}
else
if (ll4 == 0) {
ll4 = 1;
h --;
}
}
g = 1ll * g * (1ll << h);
}
g = 1ll * g * (k - i + 1) * (l - j + 1);
adunare (g);
//aria = 1LL * aria + (k - i + 1) * (j - l + 1);
}
}
cmmdc = gcd ();
impartire (aria, cmmdc, ans);
if (cmmdc)
num = 1ll * num / cmmdc;
for (i = 1; i <= ans [0]; i ++)
printf ("%d", ans [i]);
printf ("/%d\n", num);
}
int main () {
int T, t;
freopen ("boundingbox.in", "r", stdin);
freopen ("boundingbox.out", "w", stdout);
scanf ("%d", &T);
for (t = 1; t <= T; t ++) {
read ();
solve ();
reset ();
}
return 0;
}