Cod sursa(job #115887)

Utilizator hadesgamesTache Alexandru hadesgames Data 17 decembrie 2007 12:56:36
Problema Zone Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.13 kb
#include <stdio.h>
int c[600][600],a[10],b[600][600],l1,l2,c1,c2,d[20],e[20],x,y,z,t,n;
int ver(int x)
{
	int f,i;
	f=0;
	for (i=1;i<=9;i++)
		e[i]=1;
	for (i=1;i<=9;i++)
	if (e[i]&&a[i]==c[l1][c1])
	{
		e[i]=0;
		f=1;
		break;
	}
	if (!f)
		return 0;
	f=0;
	for (i=1;i<=9;i++)
	if (e[i]&&a[i]==c[l1][c2]-c[l1][c1])
	{
		e[i]=0;
		f=1;
		break;
	}
	if (!f)
		return 0;
	f=0;
	for (i=1;i<=9;i++)
	if (e[i]&&a[i]==c[l1][n]-c[l1][c2])
	{
		e[i]=0;
		f=1;
		break;
	}
	if (!f)
		return 0;
	f=0;
	for (i=1;i<=9;i++)
	if (e[i]&&a[i]==c[l2][c1]-c[l1][c1])
	{
		e[i]=0;
		f=1;
		break;
	}
	if (!f)
		return 0;
	f=0;
	for (i=1;i<=9;i++)
	if (e[i]&&a[i]==c[l2][c2]-c[l2][c1]-c[l1][c2]+c[l1][c1])
	{
		e[i]=0;
		f=1;
		break;
	}
	if (!f)
		return 0;
	f=0;
	for (i=1;i<=9;i++)
	if (e[i]&&a[i]==c[l2][n]-c[l1][n]-c[l2][c2]+c[l1][c2])
	{
		e[i]=0;
		f=1;
		break;
	}
	if (!f)
		return 0;
	f=0;
	for (i=1;i<=9;i++)
	if (e[i]&&a[i]==c[n][c1]-c[l2][c1])
	{
		e[i]=0;
		f=1;
		break;
	}
	if (!f)
		return 0;
	f=0;
	for (i=1;i<=9;i++)
	if (e[i]&&a[i]==c[n][c2]-c[n][c1]-c[l2][c2]+c[l2][c1])
	{
		e[i]=0;
		f=1;
		break;
	}
	if (!f)
		return 0;
	f=0;
	for (i=1;i<=9;i++)
	if (e[i]&&a[i]==c[n][n]-c[l2][n]-c[n][c2]+c[l2][c2])
	{
		e[i]=0;
		f=1;
		break;
	}
	if (!f)
		return 0;
	return 1;
}
int ver2(int x)
{
	int i;
	i=1;
	if (l1<x)
		return 1;
	if (l1>x)
		return 0;
	if (c1<z)
		return 1;
	if (c1>z)
		return 0;
	if (l2<y)
		return 1;
	if (l2>y)
		return 0;
	if (c2<t)
		return 1;
	if (c2>t)
		return 0;
	if (i==1)
		return 0;
}
int cauta(int x,int val)
{
	int m,p,u;
	p=x; 
	u=n;
	while (p<u)
	{
		m=(p+u)/2;
		if (c[m][c1]-c[x-1][c1]==val)
			return m;
		if (c[l1][m]-c[l1][x-1]<val)
			p=m+1;
		else
			u=m;
	}
	if (c[l1][p]-c[l1][x-1]==val)
		return p;
	return -1;
}
int cauta2(int x,int val)
{
	int m,p,u;
	p=x; 
	u=n;
	while (p<u)
	{
		m=(p+u)/2;
		if (c[m][c1]-c[x-1][c1]==val)
			return m;
		if (c[m][c1]-c[x-1][c1]<val)
			p=m+1;
		else
			u=m;
	}
	if (c[p][c1]-c[x-1][c1]==val)
		return p;
	return -1;
}
	
int main()
{
	int i2,i,j;
	FILE *in,*out;
	in=fopen("zone.in","r");
	out=fopen("zone.out","w");
	fscanf(in,"%d",&n);
	for (i=1;i<=9;i++)
		fscanf(in,"%d",&a[i]);
		
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=n;j++)
		{
			fscanf(in,"%d",&b[i][j]);
			c[i][j]=c[i-1][j]+c[i][j-1]-c[i-1][j-1]+b[i][j];
		}
	}
	x=600;
	y=600;
	z=600;
	t=600;
	for (l1=1;l1<=n;l1++)
	{
		for (j=1;j<=9;j++)
		{
			d[j]=1;
			c1=cauta(1,a[j]);
			if (c1!=-1)
				for (i=1;i<=9;i++)
				if (!d[i])
				{ 
					d[i]=1;
					c2=cauta(c1+1,a[i]);
					if (c2!=-1)
					{
						for (i2=1;i2<=9;i2++)
						if (!d[i2])
						{
							d[i2]=1;
							l2=cauta2(l1+1,a[i2]);
							if (l2!=-1)
							{
								if(ver(1))
								{
									if (ver2(1))
									{
										x=l1;
										y=l2;
										z=c1;
										t=c2;
									}
								}
								
							}
							d[i2]=0;
						}
					}
					d[i]=0;
				}
			d[j]=0;
		}
	}
	fprintf(out,"%d %d %d %d\n",x,y,z,t);
	fclose(in);
	fclose(out);
	return 0;
}