Cod sursa(job #195682)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 20 iunie 2008 20:12:53
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include<stdio.h>
#define NMAX 512

int exista(unsigned long long v[],int n,unsigned long long x){
int i;
for(i=0;i<n;++i){
	if(x==v[i]) return 1;
	else if(x<v[i]) return 0;
	}
return 0;
}

int main(){
freopen("zone.in","r",stdin);
freopen("zone.out","w",stdout);
unsigned long long a[NMAX][NMAX]={{0UL}},l,u,cr; //left,up,cross
unsigned long long z[9],wc[9],w2[36],w3[84],t,w2c[36],w3c[84];
int n,i,j,k,k2,l1,l2,c1,c2,x,nrs,nou,nr2,logic;
l=u=cr=0UL;
scanf("%d",&n);
for(k=0;k<9;++k)
	scanf("%llu",&z[k]);

for(k=0;k<9;++k) wc[k]=z[k];
for(i=0;i<8;++i)
	for(j=i+1;j<9;++j)
		if(wc[i]>wc[j])
		{t=wc[i];wc[i]=wc[j];wc[j]=t;}
k2=0;
for(i=0;i<8;++i)
	for(j=i+1;j<9;++j)
		w2[k2++]=z[i]+z[j];
for(i=0;i<35;++i)
	for(j=i+1;j<36;++j)
		if(w2[i]>w2[j]){
			t=w2[i];w2[i]=w2[j];w2[j]=t;
			}
nr2=0;
for(i=0;i<36;++i){
	nou=1;
	for(j=0;j<nr2&&nou;++j)
		nou=w2[i]!=w2c[j];
	if(nou) {w2c[nr2]=w2[i];nr2++;}
	}

k2=0;
for(i=0;i<7;++i)
	for(j=i+1;j<8;++j)
		for(k=j+1;k<9;++k)
			w3[k2++]=z[i]+z[j]+z[k];
for(i=0;i<83;++i)
	for(j=i+1;j<84;++j)
		if(w3[i]>w3[j]){
			t=w3[i];w3[i]=w3[j];w3[j]=t;
			}
nrs=0;
for(i=0;i<84;++i){
	nou=1;
	for(j=0;j<=nrs&&nou;++j)
		nou=w3[i]!=w3c[j];
	if(nou) {w3c[nrs]=w3[i];nrs++;}
	}
for(i=0;i<n;++i){
	l=0UL;cr=0UL;
	for(j=0;j<n;++j){
		if(i) u=a[i-1][j];
		else u=0UL;
		scanf("%d",&x);
		a[i][j]=x+l+u-cr;
		l=a[i][j];
		cr=u;
		}
	}
for(l1=0;l1<n-2;++l1){
	for(c1=0;c1<n-2;++c1){
		logic=exista(wc,9,a[l1][c1])&&
			  exista(w3c,nrs,a[l1][n-1])&&
			  exista(w3c,nrs,a[n-1][c1]);
		if(logic)
			for(l2=l1+1;l2<n-1;++l2)
				for(c2=c1+1;c2<n-1;++c2){
					logic=exista(wc,9,a[l2][c2]+a[l1][c1]-a[l1][c2]-a[l2][c1])&&
					   exista(wc,9,a[l2][c1]-a[l1][c1])&&
					   exista(wc,9,a[l1][c2]-a[l1][c1])&&
					   exista(w2c,nr2,a[l2][c2]-a[l1][c2])&&
					   exista(w2c,nr2,a[l2][c2]-a[l2][c1])&&
					   exista(w3c,nrs,a[l2][n-1]-a[l1][n-1])&&
					   exista(w3c,nrs,a[n-1][c2]-a[n-1][c1]);
				   if(logic) goto finish;
				}
		}
	}
finish:
printf("%d %d %d %d",l1+1,l2+1,c1+1,c2+1);
return 0;
}