Cod sursa(job #18202)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 18 februarie 2007 10:37:29
Problema Zone Scor 80
Compilator c Status done
Runda preONI 2007, Runda 2, Clasa a 9-a si gimnaziu Marime 2.71 kb
#include <stdio.h>

#define MAXN 515

int N;
long long S[10]; int uS[10];

int l1, c1, l2, c2;
int sl1, sc1, sl2, sc2;

int x[MAXN][MAXN];
long long s[MAXN][MAXN];

int st[10];

int bin_search( long long S, int f )
{
	int step = 256, i;
	for (i = f; step; step >>= 1)
		if (i + step <= N && s[l1][i + step] - s[l1][f] < S)
			i += step;
	i++;
	if (i > N || s[l1][i] - s[l1][f] != S)
		return -1;
	return i;
}

int find( long long val )
{
	int i;
	for (i = 0; i < 9; i++)
		if (!uS[i] && S[i] == val)
			return i;
	return -1;
}

int ok( long long S2[10] )
{
	int i, st[10];
	for (i = 4; i < 9; i++)
	{
		st[i] = find( S2[i] );
		if (st[i] == -1)
		{
			for (i--; i >= 4; i--)
				uS[ st[i] ] = 0;
			return 0;
		}
		uS[ st[i] ] = 1;
	}
	for (i = 4; i < 9; i++)
		uS[ st[i] ] = 0;
	return 1;
}

void newsol( int l1, int l2, int c1, int c2 )
{
	sl1 = l1;
	sl2 = l2;
	sc1 = c1;
	sc2 = c2;
}

void getotherlines()
{
	c1 = bin_search( S[ st[0] ], 0 );		// taietura 1..c1; c1 + 1 .. c2; c2 + 1 .. N
	if (c1 == -1)
		return;

	c2 = bin_search( S[ st[1] ], c1 );
	if (c2 == -1)
		return;

	if (s[l1][N] - s[l1][c2] != S[ st[2] ])
		return;

	//mai ramane de terminat l2
	
	long long S2[10];
	S2[0] = S[ st[0] ];
	S2[1] = S[ st[1] ];
	S2[2] = S[ st[2] ];
	for (l2 = l1 + 1; l2 <= N; l2++)
	{
		S2[3] = s[l2][c1] - s[l1][c1];
		S2[4] = s[l2][c2] - s[l1][c2] - S2[3];
		S2[5] = s[l2][N] - s[l1][N] - S2[3] - S2[4];

		S2[6] = s[N][c1] - s[l2][c1];
		S2[7] = s[N][c2] - s[l2][c2] - S2[6];
		S2[8] = s[N][N] - s[l2][N] - S2[6] - S2[7];

	
		if (!ok( S2 ))
			continue;

		//avem solutie <:-P
	
		if (sl1 == 0)		//asta e prima solutie gasita
			newsol( l1, l2, c1, c2 );
		else
		{
			if (l1 < sl1)
			{
				newsol( l1, l2, c1, c2 );
				continue;
			}
			if (l1 > sl1)
				continue;

			if (c1 < sc1)
			{
				newsol( l1, l2, c1, c2 );
				continue;
			}
			if (c2 > sc1)
				continue;

			if (l2 < sl2)
			{
				newsol( l1, l2, c1, c2 );
				continue;
			}
			if (l2 > sl2)
				continue;

			if (c2 < sc2)
				newsol( l1, l2, c1, c2 );
		}
	}

	return;
}

void picksums(int k)
{
	if (k == 3)
	{
		getotherlines();
		return;
	}

	int i = 0;
	if (k)
		i = st[k - 1] + 1;
	for (; i < 9; i++)
	{
		st[k] = i;
		uS[i] = 1;
		picksums(k + 1);
		uS[i] = 0;
	}
}

int main()
{
	freopen("zone.in", "rt", stdin);
	freopen("zone.out", "wt", stdout);
	scanf("%d", &N);
	int i, j;
	for (i = 0; i < 9; i++)
		scanf("%lld", S + i);
	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
		{
			scanf("%d", x[i] + j);
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (long long)x[i][j];
		}

	for (l1 = 1; l1 <= N - 1; l1++)				//tai intre 1..l1 si l1+1..N
	{
		//determini c1 si c2 pentru orice alegere a primelor 3 sume
		picksums(0);
	}

	printf("%d %d %d %d\n", sl1, sl2, sc1, sc2);
	return 0;
}