Cod sursa(job #131235)

Utilizator razvi9Jurca Razvan razvi9 Data 3 februarie 2008 14:34:35
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include<cstdio>
const int N=513;
int a[N][N],n,i,j,s1,s2,s4,s[9],S[9],used[9],l1,l2,c1,c2,L1,L2,C1,C2;

int search_c1(int st,int dr,int s)
{if(st>dr) return 0;
 int mij=(st+dr)/2;
 if(a[l1][mij]==s) return mij;
 if(a[l1][mij]>s) return search_c1(st,mij-1,s);
 return search_c1(mij+1,dr,s);}

int search_l2(int st,int dr,int s)
{if(st>dr) return 0;
 int mij=(st+dr)/2;
 int s1=a[mij][c1]-a[l1][c1];
 if(s1==s) return mij;
 if(s1>s) return search_l2(st,mij-1,s);
 return search_l2(mij+1,dr,s);}

int search_c2(int st,int dr,int s)
{if(st>dr) return 0;
 int mij=(st+dr)/2;
 int s1=a[l1][mij]-a[l1][c1];
 if(s1==s) return mij;
 if(s1>s) return search_c2(st,mij-1,s);
 return search_c2(mij+1,dr,s);}

int ver()
{for(i=0;i<9;i++) used[i]=0;
 S[0]=s[s1];
 S[1]=s[s2];
 S[2]=a[l1][n]-a[l1][c2];
 S[3]=s[s4];
 S[4]=a[l2][c2]-a[l2][c1]-a[l1][c2]+a[l1][c1];
 S[5]=a[l2][n]-a[l2][c2]-a[l1][n]+a[l1][c2];
 S[6]=a[n][c1]-a[l2][c1];
 S[7]=a[n][c2]-a[n][c1]-a[l2][c2]+a[l2][c1];
 S[8]=a[n][n]-a[n][c2]-a[l2][n]+a[l2][c2];
 for(i=0;i<9;i++){
	 for(j=0;j<9;j++)
		 if(S[i]==s[j]&&!used[j]) {used[j]=1;break;}
	 if(j==9) return 0;}
 return 1;}

inline void update()
{L1=l1;L2=l2;C1=c1;C2=c2;};

inline void update_sol()
{if(!L1){update();return;}
 if(l1<L1) {update();return;}
 else
	 if(l1==L1) 
		 if(c1<C1) {update();return;}
		 else
			 if(c1==C1)
				 if(l2<L2) {update();return;}
				 else
					 if(l2==L2)
						 if(c2<C2) {update();return;}}


int main()
{
	freopen("zone.in","r",stdin);
	freopen("zone.out","w",stdout);
	scanf("%d",&n);
	for(i=0;i<9;i++)scanf("%d",&s[i]);
	for(i=1;i<=n;i++)		
		for(j=1;j<=n;j++){
			scanf("%d",&a[i][j]);
			a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];}


	for(s1=0;s1<9;s1++)
		for(l1=1;l1<n-1;l1++)
		{
			c1=search_c1(1,n-2,s[s1]);
			if(!c1) continue;
			for(s4=0;s4<9;s4++)
				if(s4!=s1)
				{
					l2=search_l2(l1+1,n-1,s[s4]);
					if(!l2) continue;
					for(s2=0;s2<9;s2++)
						if(s2!=s1&&s2!=s4)
						{
							c2=search_c2(c1+1,n-1,s[s2]);
							if(!c2) continue;
							if(ver()) update_sol();
						}
				}
		}
	printf("%d %d %d %d\n",L1,L2,C1,C2);
	fclose(stdout);
	return 0;
}