Pagini recente » Cod sursa (job #221128) | Cod sursa (job #901545) | Cod sursa (job #427899) | Cod sursa (job #1730906) | Cod sursa (job #360858)
Cod sursa(job #360858)
#include <stdio.h>
#include <algorithm>
#define Nmax 513
#define LL long long // NU UITA
using namespace std;
LL s[Nmax][Nmax];
LL z[10];
int a[Nmax][Nmax],use[10];
int n,i1,col1,col2,i2;
void read(){
int i,j;
freopen("zone.in","r",stdin);
freopen("zone.out","w",stdout);
scanf("%d",&n);
for(i=1;i<10;++i) scanf("%lld",&z[i]);
sort(z+1,z+10);
for(i=1;i<=n;++i)
for(j=1;j<=n;++j) scanf("%d",&a[i][j]);
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
}
int caut_bin(int l,int r,LL x){
int m;
while(l<=r){
m=l+(r-l)/2;
if(s[i1][m]-s[i1][col1] == x) return m;
if( s[i1][m]-s[i1][col1] < x) l=m+1;
else r=m-1;
}
return -1;
}
int caut_bin2(LL x){
int m,l=1,r=9,ret=-1;
while(l<=r){
m=l+(r-l)/2;
if(z[m] == x){ ret=m; r=m-1; }
else if(z[m] > x) r=m-1;
else l=m+1;
}
if( ret != -1 ) use[ret]=1;
return ret;
}
int search(){
int i,p1,p2,p3,p4,p5,p6; LL z1,z2,z3,z4,z5,z6;
for(i=i1+1;i<=n;++i){
z1 = s[i][col1] - s[i1][col1];
p1 = caut_bin2(z1);
if( p1 != -1){
z2 = s[i][col2] - s[i][col1] - s[i1][col2] + s[i1][col1];
p2 = caut_bin2(z2);
if( p2 != -1){
z3 = s[i][n] - s[i][col2] - s[i1][n] + s[i1][col2];
p3 = caut_bin2(z3);
if( p3 != -1){
z4 = s[n][col1] - s[i][col1];
p4 = caut_bin2(z4);
if( p4 != -1){
z5 = s[n][col2] - s[n][col1]- s[i][col2] + s[i][col1];
p5 = caut_bin2(z5);
if( p5 != -1){
z6 = s[n][n] - s[n][col2] - s[i][n] + s[i][col2];
p6 = caut_bin2(z6);
if( p6 != -1 ){ i2=i; return 1; }
use[p6]=0;
}
use[p5]=0;
}
use[p4]=0;
}
use[p3]=0;
}
use[p2]=0;
}
use[p1]=0;
}
return 0;
}
void solve(){
int i,j,poz; LL suma3;
for(i1=1;i1<=n;++i1)
for(i=1; i<=9; ++i){ // caut prima zona cu suma z[i1]
use[i]=1;
col1=caut_bin(1,n,z[i]);
if(col1 != -1){
for(j=1;j<=9;++j)
if(!use[j]){
use[j]=1;
col2=caut_bin(col1+1,n,z[j]);
if(col2 != -1){
suma3= s[i1][n]-s[i1][col2];
poz = caut_bin2(suma3);
if( poz!=-1 ){
if( search() ) return;
use[poz]=0;
}
}
use[j]=0;
}
}
use[i]=0;
}
}
int main(){
read();
solve();
printf("%d %d %d %d\n",i1,i2,col1,col2);
fclose(stdin); fclose(stdout);
return 0;
}