Pagini recente » Cod sursa (job #1733) | Cod sursa (job #788466) | Cod sursa (job #2359372) | Cod sursa (job #2173931) | Cod sursa (job #1724238)
#include <fstream>
#include <algorithm>
#define NMAX 520
using namespace std;
long long int patratele[10],sum[NMAX][NMAX],casuta1,casuta2,casuta3,casuta4,casuta5,casuta6,casuta7,casuta8,casuta9;
int v[NMAX][NMAX],i,j,n,col1,col2,lin1,lin2,x5,x6,test,x7,da,x8,da1,ans1,ans2,ans3,ans4;
void suma()
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+v[i][j];
}
bool check2(long long a)
{
if(sum[lin1][a]<casuta1)
return 0;
else
return 1;
}
bool check1(long long a)
{
if(sum[lin1][a]-casuta1<casuta2)
return 0;
return 1;
}
bool check(long long a)
{
if(sum[a][col1]-casuta1<casuta4)
return 0;
return 1;
}
bool verificare()
{
int b1=1,b2=1,b3=1,b4=1,b5=1,b6=1;
casuta3=sum[lin1][n]-casuta1-casuta2;
for(i=1;i<=9;i++)
if(casuta3==patratele[i])
b1=0;
casuta5=sum[lin2][col2]-casuta1-casuta2-casuta4;
for(i=1;i<=9;i++)
if(casuta5==patratele[i])
b2=0;
casuta6=sum[lin2][n]-casuta1-casuta2-casuta3-casuta5-casuta4;
for(i=1;i<=9;i++)
if(casuta6==patratele[i])
b3=0;
casuta7=sum[n][col1]-casuta1-casuta4;
for(i=1;i<=9;i++)
if(casuta7==patratele[i])
b4=0;
casuta8=sum[n][col2]-casuta1-casuta2-casuta4-casuta5-casuta7;
for(i=1;i<=9;i++)
if(casuta8==patratele[i])
b6=0;
casuta9=sum[n][n]-casuta1-casuta2-casuta3-casuta4-casuta5-casuta6-casuta7-casuta8;
for(i=1;i<=9;i++)
if(casuta9==patratele[i])
b5=0;
if(b1==0 && b2==0 && b3==0 && b4==0 && b5==0 && b6==0)
return 1;
else
return 0;
}
int cautbinlin2()
{
int start=0;
int step=1;
for(;step<n;step<<=1);
for(;step;step>>=1)
{
int index=start+step;
if(index>=n)
continue;
if(check(index)==0)
start=index;
}
return start;
}int cautbincol2()
{
int start=0;
int step=1;
for(;step<n;step<<=1);
for(;step;step>>=1)
{
int index=start+step;
if(index>=n)
continue;
if(check1(index)==0)
start=index;
}
return start;
}
int cautbincol1()
{
int start=0;
int step=1;
for(;step<n;step<<=1);
for(;step;step>>=1)
{
int index=start+step;
if(index>=n)
continue;
if(check2(index)==0)
start=index;
}
return start;
}
int main()
{
ifstream f("zone.in");
ofstream g("zone.out");
f>>n;
for(i=1;i<=9;i++)
f>>patratele[i];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
f>>v[i][j];
}
sort(patratele+1,patratele+10);
suma();
/*for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
g<<sum[i][j]<<" ";
g<<"\n";
}
*/
for(x5=1;x5<=n-1;x5++)
{
lin1=x5;
for(x8=1;x8<=9;x8++)
{
casuta1=patratele[x8];
test=cautbincol1()+1;
if(sum[lin1][test]==casuta1)
{
col1=test;
}
else continue;
for(x6=1;x6<=9;x6++)
{
casuta4=patratele[x6];
test=cautbinlin2()+1;
//g<<test<<" "<<casuta4<<" "<<lin1<<" "<<col1<<" "<<casuta1<<"\n";
if(sum[test][col1]-casuta1==casuta4 && test!=lin1)
{
lin2=test;
//g<<lin1<<" "<<lin2<<" "<<col1<<" "<<casuta1<<" "<<casuta4;
}
else continue;
for(x7=1;x7<=9;x7++)
{
casuta2=patratele[x7];
test=cautbincol2()+1;
//g<<test<<" "<<lin1<<" "<<lin2<<" "<<col1<<" "<<col2<<" "<<casuta2<<"\n";
if(sum[lin1][test]-casuta1==casuta2 && test!=col1)
{
col2=test;
// g<<lin1<<" "<<lin2<<" "<<col1<<" "<<col2<<" "<<casuta2<<"\n";
}
else continue;
//g<<lin1<<" "<<lin2<<" "<<col1<<" "<<col2<<" "<<casuta2<<"\n";
da=verificare();
//g<<da<<"\n";
//g<<lin1<<" "<<lin2<<" "<<col1<<" "<<col2<<" "<<casuta1<<" "<<casuta2<<" "<<casuta3<<" "<<casuta4<<" "<<casuta5<<" "<<casuta6<<" "<<casuta7<<" "<<casuta8<<" "<<casuta9<<"\n";
if(da==1 && da1==0)
{
ans1=lin1;
ans2=lin2;
ans3=col1;
ans4=col2;
da1=1;
}
}
}
}
}
g<<ans1<<" "<<ans2<<" "<<ans3<<" "<<ans4;
}