Pagini recente » Cod sursa (job #125828) | Cod sursa (job #86789) | Cod sursa (job #2730964) | Cod sursa (job #2884491) | Cod sursa (job #2357488)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
int n,i,j,k,q,v[10],l1,l2,c1,c2;
long long s[515][515];
bool f[10];
int C1(int S){
int st=1,dr=n-2,mij,sol=0;
while(st<=dr){
mij=(st+dr)/2;
if(s[l1][mij]==S){
sol=mij;
dr=mij-1;
}
else
st=mij+1;
}
return sol;
}
int C2(int S){
int st=c1+1,dr=n-2,mij,sol=0;
while(st<=dr){
mij=(st+dr)/2;
if(s[l1][mij]-s[l1][c1]==S){
sol=mij;
dr=mij-1;
}
else
st=mij+1;
}
return sol;
}
int L2(int S){
int st=l1+1,dr=n-1,mij,sol=0;
while(st<=dr){
mij=(st+dr)/2;
if(s[mij][c1]-s[mij-1][c1]==S){
sol=mij;
dr=mij-1;
}
else
st=mij+1;
}
return sol;
}
bool valid(){
///VERIFIC S5
int s5 = s[l2][c2]-s[l2][c1]-s[l1][c2]+s[l1][c1];
int poz5 = 0;
for(int i=1;i<=9 && !poz5;i++)
if(f[i]==0 && v[i]==s5){
poz5=i;
f[i]=1;
}
if(!poz5){
f[poz5]=0;
return 0;
}
///VERIFIC S6
int s6 = s[l2][n]-s[l2][c2]-s[l1][n]+s[l1][c2];
int poz6 = 0;
for(int i=1;i<=9 && !poz6;i++)
if(f[i]==0 && v[i]==s6){
poz6=i;
f[i]=1;
}
if(!poz6){
f[poz5]=f[poz6]=0;
return 0;
}
///VERIFIC S7
int s7 = s[n][c1]-s[l2][c1];
int poz7 = 0;
for(int i=1;i<=9 && !poz7;i++)
if(f[i]==0 && v[i]==s7){
poz7=i;
f[i]=1;
}
if(!poz7){
f[poz5]=f[poz6]=f[poz7]=0;
return 0;
}
///VERIFIC S8
int s8 = s[n][c2]-s[n][c1]-s[l2][c2]+s[l2][c1];
int poz8 = 0;
for(int i=1;i<=9 && !poz8;i++)
if(f[i]==0 && v[i]==s8){
poz8=i;
f[i]=1;
}
if(!poz8){
f[poz5]=f[poz6]=f[poz7]=f[poz8]=0;
return 0;
}
///VERIFIC S9
int s9 = s[n][n]-s[n][c2]-s[l2][n]+s[l2][c2];
int poz9 = 0;
for(int i=1;i<=9 && !poz9;i++)
if(f[i]==0 && v[i]==s9){
poz9=i;
f[i]=1;
}
if(!poz9){
f[poz5]=f[poz6]=f[poz7]=f[poz8]=f[poz9]=0;
return 0;
}
return 1;
}
int main(){
fin>>n;
for(i=1;i<=9;i++)
fin>>v[i];
sort(v+1,v+10);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
fin>>s[i][j];
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
for(l1=1;l1<n-1;l1++){
for(i=1;i<=9;i++){
c1=0;
if(C1(v[i])!=0){ // fixez C1
c1=C1(v[i]);
f[i]=1;
/// CAUT C2
for(j=1;j<=9;j++)
if(!f[j] && C2(v[j])!=0){
c2=C2(v[j]);
f[j]=1;
/// CAUT L2
for(k=1;k<=9;k++)
if(!f[k] && L2(v[k])!=0){
l2=L2(v[k]);
f[k]=1;
///Verific daca este buna configuratia
if(valid()){
fout<<l1<<' '<<l2<<' '<<c1<<' '<<c2;
}
}
f[j]=0;
}
f[i]=0;
}
}
}
return 0;
}