Cod sursa(job #20142)

Utilizator damaDamaschin Mihai dama Data 20 februarie 2007 19:35:49
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <stdio.h>
const int nmax = 513;

void bkt(int k);
int n, used[11], sz[11], mat[nmax][nmax], s[nmax][nmax], suma[11], sl1 = 10000, sc1, sl2, sc2;

int main()
{
	freopen("zone.in","r",stdin);
	freopen("zone.out","w",stdout);

	int i, j;
	scanf("%d", &n);
	for(i =  1; i < 10; ++i)
	{
		scanf("%d", &suma[i]);
	}
	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= n; ++j)
		{
			scanf("%d", &mat[i][j]);
			s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j -  1] + mat[i][j];
		}
	}
	bkt(1);
        printf("%d %d %d %d\n", sl1, sl2, sc1, sc2); 
	return 0;
}

void bkt(int k)
{
	int i;
	if(k == 10)
	{
		int min = 1, mid, max = n - 1, x, l1, l2, c1, c2, found = 0;
		x = suma[sz[1]] + suma[sz[2]] + suma[sz[3]];
		while(min <= max)
		{
			mid = (min + max) / 2;
			if(s[mid][n] == x)
			{
				found = 1;
				break;
			}
			else if(s[mid][n] < x)
			{
				min = mid + 1;
			}
			else
			{
				max = mid - 1;
			}
		}
		if(!found)
			return;
		l1 = mid;
		min = l1 + 1;
		max = n - 1;
		x = suma[sz[4]] + suma[sz[5]] + suma[sz[6]];
		found = 0;
		while(min <= max)
		{
			mid = (min + max) / 2;
			if(s[mid][n] - s[l1][n] == x)
			{
				found = 1; 
				break;
			}
			else if(s[mid][n] - s[l1][n] < x)
			{
				min = mid + 1;
			}
			else
			{
				max = mid - 1;
			}
		}
		if(!found)
			return;
		l2 = mid;
		
		min = 1;
		max = n - 1;
		x = suma[sz[1]];
		found = 0;
		while(min <= max)
		{
			mid = (min + max) / 2;
			if(x == s[l1][mid])
			{
				found = 1;
				break;
			}
			else if(x > s[l1][mid])
			{
				min = mid + 1;
			}
			else
			{
				max = mid - 1;
			}
		}
		if(!found || s[l2][mid] - s[l1][mid] != suma[sz[4]] || s[n][mid] - s[l2][mid] != suma[sz[7]])
			return;
		c1 = mid;
		found = 1;
		min = c1 + 1;
		max = n - 1;
		x = suma[sz[2]];
		while(min <= max)
		{
			mid = (min + max) / 2;
			if(x == s[l1][mid] - s[l1][c1])
			{
				found = 1;
				break;
			}
			else if(x > s[l1][mid] - s[l1][c1])
			{
				min = mid + 1;
			}
			else
			{
				max = mid - 1;
			}
		}
		
		if(!found || s[l2][mid] - s[l2][c1] - s[l1][mid] + s[l1][c1] != suma[sz[5]] || suma[sz[8]] != s[n][mid] - s[n][c1] - s[l2][mid] + s[l2][c1])
			return;
		c2 = mid;
		if(l1 < sl1 || (l1 == sl1 && c1 < sc1) || (l1 == sl1 && c1 == sc1 && l2 < sl2) || (l1 + l2 + c1 + c2 < sl1 + sl2 + sc1 + sc2))
		{
			sl1 = l1;
			sl2 = l2;
			sc1 = c1;
			sc2 = c2;
//			printf("%d %d %d  %d\n",sz[4], sz[5],sz[6], x);
		}
	}
	else
	{
		for(i = 1; i < 10; ++i)
		{
			if(!used[i])
			{
				sz[k] = i;
				used[i] = 1;
				bkt(k + 1);
				used[i] = 0;
                                sz[k] = 0;
			}
		}
	}
}