Pagini recente » Cod sursa (job #552007) | Cod sursa (job #1204604) | Cod sursa (job #2414860) | Cod sursa (job #327238) | Cod sursa (job #2070679)
#include <cstdio>
#include <bitset>
using namespace std;
long long s[9],a[513][513];
bitset <9> f;
int verif (long long sum){
int i;
for (i=1;i<=9;i++){
if (s[i]==sum && f[i]==0){
f[i]=1;
return 1;
}
}
return 0;
}
int main()
{
FILE *fin=fopen ("zone.in","r");
FILE *fout=fopen ("zone.out","w");
int n,i,j,s1,s2,s3,l1,c1,c2,st,dr,mid;
long long sum;
fscanf (fin,"%d",&n);
for (i=1;i<=9;i++)
fscanf (fin,"%lld",&s[i]);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++){
fscanf (fin,"%lld",&a[i][j]);
a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
for (s1=1;s1<=9;s1++){
for (s2=1;s2<=9;s2++){
for (s3=1;s3<=9;s3++){
// stiu s1,s2,s3
//if (s1==2 && s2==3 && s3==6)
// printf ("a");
if (s1==s2 || s2==s3 || s1==s3)
continue;;
for (i=1;i<n;i++){ // caut L1=i
if (a[i][n]!=s[s1]+s[s2]+s[s3])
continue;
l1=i;
st=1;
dr=n;
while (st<=dr){
mid=(st+dr)/2;
if (a[l1][mid]==s[s1])
break;
else if (a[l1][mid]<s[s1])
st=mid+1;
else dr=mid-1;
}
if (st>dr)
continue; // nu exista niciun C1 posibil pt L1=i si s1
c1=mid;
// am c1 fixat, acum vreau sa il caut pe c2
st=c1+1;
dr=n;
while (st<=dr){
mid=(st+dr)/2;
if (a[l1][mid]-a[l1][c1]==s[s2])
break;
else if (a[l1][mid]-a[l1][c1]<s[s2])
st=mid+1;
else dr=mid-1;
}
if (st>dr)
continue;
c2=mid;
// fac un for pt a fixa l2 si verific
for (j=i+1;j<=n;j++){
f.reset();
f[s1]=f[s2]=f[s3]=1;
sum=a[j][c1]-a[i][c1];
if (verif(sum)==0)
continue;
sum=a[j][c2]-a[j][c1]-a[i][c2]+a[i][c1];
if (verif (sum)==0)
continue;
sum=a[j][n]-a[i][n]-a[j][c2]+a[i][c2];
if (verif (sum)==0)
continue;
sum=a[n][c1]-a[j][c1];
if (verif (sum)==0)
continue;
sum=a[n][c2]-a[n][c1]-a[j][c2]+a[j][c1];
if (verif (sum)==0)
continue;
fprintf (fout,"%d %d %d %d",l1,j,c1,c2);
return 0;
}
}
}
}
}
return 0;
}