Cod sursa(job #1230820)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 19 septembrie 2014 11:50:10
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 3.62 kb
#include <fstream>
using namespace std;

const int MAX_N = 52;

int T, N, M;
int A[MAX_N][MAX_N], S[MAX_N][MAX_N], pow2[62];
char s[MAX_N + 5];

int countOnes(int x1, int y1, int x2, int y2) {
	if(x1 > x2 || y1 > y2)
		return 0;

	return S[x2][y2] - S[x2][y1 - 1] - S[x1 - 1][y2] + S[x1 - 1][y1 - 1];
}

long long gcd(long long a, long long b) {
	while(b) {
		long long r = a % b;

		a = b;
		b = r;
	}

	return a;
}

int main() {
	ifstream f("boundingbox.in");
	ofstream g("boundingbox.out");

	s[0] = ' ';

	pow2[0] = 1;
	for(int i = 1; i <= 60; ++i)
		pow2[i] = pow2[i - 1] * 2;

	f >> T;
	for(int t = 1; t <= T; ++t) {
		f >> N >> M;

		for(int i = 1; i <= N; ++i) {
			f >> (s + 1);

			for(int j = 1; j <= M; ++j)
				A[i][j] = s[j] - '0';
		}

		for(int i = 1; i <= N; ++i)
			for(int j = 1; j <= M; ++j)
				S[i][j] = A[i][j] + S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1];

		long long a = 0, b = 0;
		for(int x1 = 1; x1 <= N; ++x1)
			for(int x2 = x1; x2 <= N; ++x2)
				for(int y1 = 1; y1 <= M; ++y1)
					for(int y2 = y1; y2 <= M; ++y2) {
						int cntX1 = countOnes(x1, y1 + 1, x1, y2 - 1),
							cntX2 = countOnes(x2, y1 + 1, x2, y2 - 1),
							cntY1 = countOnes(x1 + 1, y1, x2 - 1, y1),
							cntY2 = countOnes(x1 + 1, y2, x2 - 1, y2),
							total = countOnes(x1 + 1, y1 + 1, x2 - 1, y2 - 1);

						long long now = 0;
						now = (pow2[cntX1] - 1) * (pow2[cntY1] - 1) * (pow2[cntX2] - 1) * (pow2[cntY2 - 1] - 1);
						a += now * (x2 - x1 + 1) * (y2 - y1 + 1);

                        int t;
						if(x1 == x2 && y1 == y2)
                            a += A[x1][y1];
                        else if(x1 == x2) {
                            t = A[x1][y1] + A[x1][y2];
                            if(t == 2)
                                a += pow2[cntX1] * pow2[total] * (y2 - y1 + 1);
                        }
                        else if(y1 == y2) {
                            t = A[x1][y1] + A[x2][y1];
                            if(t == 2)
                                a += pow2[cntY1] * pow2[total] * (x2 - x1 + 1);
                        }
                        else {
                            t = A[x1][y1] + A[x1][y2] + A[x2][y1] + A[x2][y2];

                            if(t == 4)
                                a += pow2[total] * pow2[cntX1] * pow2[cntX2] * pow2[cntY1] * pow2[cntY2] * 7 * (x2 - x1 + 1) * (y2 - y1 + 1);
                            else if(t == 3)
                                a += pow2[total] * pow2[cntX1] * pow2[cntX2] * pow2[cntY1] * pow2[cntY2] * 2 * (x2 - x1 + 1) * (y2 - y1 + 1);
                            else if(t == 2) {
                                long long x = pow2[total];

                                if(A[x1][y1] || A[x1][y2])
                                    x *= pow2[cntX1];
                                else x *= pow2[cntX1] - 1;
                                if(A[x2][y1] || A[x2][y2])
                                    x *= pow2[cntX2];
                                else x *= pow2[cntX2] - 1;
                                if(A[x1][y1] || A[x2][y1])
                                    x *= pow2[cntY1];
                                else x *= pow2[cntY1] - 1;
                                if(A[x1][y2] || A[x2][y2])
                                    x *= pow2[cntY2];
                                else x *= pow2[cntY2] - 1;
                                x *=  (x2 - x1 + 1) * (y2 - y1 + 1);
                                a += x;
                            }
                        }
					}

		b = pow2[countOnes(1, 1, N, M)];

		int d;
		do {
			d = gcd(a, b);

			a /= d;
			b /= d;
		} while (d != 1);

		g << a << "/" << b << "\n";
	}

	f.close();
	g.close();

	return 0;
}