Cod sursa(job #18857)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 18 februarie 2007 14:22:55
Problema Zone Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN 515

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

int l1, c1, l2, c2;

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 = 3; i < 8; 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 = 3; i < 8; i++)
		uS[ st[i] ] = 0;
	return 1;
}

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
		//e si minima..

		printf("%d %d %d %d\n", l1, l2, c1, c2);
		exit(0);
	}

	return;
}

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

	int i;
	for (i = 0; i < 9; i++)
	{
		if (uS[i])
			continue;

		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);		//inchid programu la prima solutie
	}

	return 0;
}