Pagini recente » Cod sursa (job #3347340) | Cod sursa (job #3320748) | Cod sursa (job #3314033) | Cod sursa (job #2980798) | Cod sursa (job #3322663)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("zone.in");
ofstream cout ("zone.out");
int n;
int sume[10];
int a[515][515];
int sump[515][515];
int s[515];
int p1x,p1y,p2x,p2y;
bool amsolutie=0;
int lr1,lr2,cr1,cr2;
int cbin(int x, int st, int dr)
{
while (st<=dr)
{
//cout<<"st: "<<st<<' '<<"dr: "<<dr<<endl;
int mij=(st+dr)/2;
if (x>sume[mij])
st=mij+1;
else
dr=mij-1;
}
if (sume[st]==x)
return 1;
else
return 0;
}
int verif(int &l1, int &l2, int &c1, int &c2)
{
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
{
p1x=i;
p1y=j;
int saux=sump[p1x][p1y];
//cout<<i<<' '<<j<<' '<<saux<<endl;
//cout<<"saux: "<<saux<<endl;
if (cbin(saux,1,9)==1)
{
//cout<<i<<' '<<j<<' '<<saux<<' '<<cbin(saux,1,9)<<endl;
for (int p=i+1; p<=n; p++)
{
bool gasit=1;
for (int q=j+1; j<=n && gasit==1; q++)
{
p2x=p;
p2y=q;
//cout<<p<<' '<<q<<endl;
//cout<<i<<' '<<j<<' '<<p<<' '<<q<<endl;
//cout<<"saux: "<<saux<<endl;
s[1]=sump[i][j];
s[2]=sump[i][q]-sump[i][j];
s[3]=sump[i][n]-sump[i][q];
s[4]=sump[p][j]-sump[i][j];
s[5]=sump[p][q]-sump[i][q]-sump[p][j]+sump[i][j];
s[6]=sump[p][n]-sump[i][n]-sump[p][q]+sump[i][q];
s[7]=sump[n][j]-sump[p][j];
s[8]=sump[n][q]-sump[p][q]-sump[n][j]+sump[p][j];
s[9]=sump[n][n]-sump[p][n]-sump[n][q]+sump[p][q];
sort(s+1,s+1+9);
for (int f=1; f<=9; f++)
if (s[f]!=sume[f])
{
gasit=0;
break;/*cout<<s[f]<<' '<<sume[f]<<' '<<gasit<<endl;*/
}
if (gasit==1)
//cout<<i<<' '<<p<<' '<<j<<' '<<q<<endl;
if (amsolutie==0){
l1=n;
l2=p;
c1=j;
c2=q;
lr1=i;
lr2=p;
cr1=j;
cr2=q;
amsolutie=1;}
}
}
}
}
}
int main()
{
cin>>n;
for (int i=1; i<=9; i++)
cin>>sume[i];
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
{
cin>>a[i][j];
sump[i][j]=a[i][j]+sump[i-1][j]+sump[i][j-1]-sump[i-1][j-1];
}
sort(sume+1,sume+1+9);
/*for (int i=1; i<=9; i++)
cout<<sume[i]<<' ';
cout<<endl;*/
/*for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
p1x=i;
p1y=j;
int saux=sump[p1x][p1y];
if (cbin(s,1,9)==1)
{
for (int p=i+1;p<=n;p++)
for (int q=j+1;j<=n;q++)
{
p2x=p;
p2y=q;
s[1]=saux;
s[2]=sump[i][q]-sump[i][j];
s[3]=sump[i][n]-sump[i][q];
s[4]=sump[p][j]-sump[i][j];
s[5]=sump[p][q]-sump[i][q]-sump[p][j]+sump[i][j];
s[6]=sump[p][n]-sump[i][n]-sump[p][q]+sump[i][q];
s[7]=sump[n][i]-sump[p][j];
s[8]=sump[n][q]-sump[p][q]-sump[n][j]+sump[p][j];
s[9]=sump[n][n]-sump[p][n]-sump[n][q]+sump[p][q];
sort(s+1,s+1+9);
for (int f=1;f<=9;f++)
if (s[f]!=sume[f])
}
}
}*/
int a=0,b=0,c=0,d=0;
verif(a,b,c,d);
//cout<<a<<' '<<b<<' '<<c<<' '<<d;
cout<<lr1<<' '<<lr2<<' '<<cr1<<' '<<cr2;
/*int i=1;
int p=3;
int j=2;
int q=3;
s[1]=sump[i][j];
s[2]=sump[i][q]-sump[i][j];
s[3]=sump[i][n]-sump[i][q];
s[4]=sump[p][j]-sump[i][j];
s[5]=sump[p][q]-sump[i][q]-sump[p][j]+sump[i][j];
s[6]=sump[p][n]-sump[i][n]-sump[p][q]+sump[i][q];
s[7]=sump[n][j]-sump[p][j];
s[8]=sump[n][q]-sump[p][q]-sump[n][j]+sump[p][j];
s[9]=sump[n][n]-sump[p][n]-sump[n][q]+sump[p][q];
sort(s+1,s+1+9);
for (int i=1; i<=9; i++)
cout<<s[i]<<' ';*/
return 0;
}