Pagini recente » Cod sursa (job #1298868) | Cod sursa (job #2336071) | Cod sursa (job #629569) | Cod sursa (job #1284871) | Cod sursa (job #132030)
Cod sursa(job #132030)
#include <stdio.h>
long n,i,j,k,r,t,q,ok;
long a,s[514][514],z[10],pus[10];
long low,high,mid,low2,high2,mid2,low3,high3,mid3;
int afisare(){
for (q=1;q<=9;q++)
pus[q]=0;
pus[j]=1;pus[k]=1;pus[r]=1;pus[t]=1;
ok=0;
for (q=1;q<=9;q++)
if (!pus[q])
if (s[mid3][mid2]-s[mid3][mid]-s[i][mid2]+s[i][mid]==z[q]){ok=1;pus[q]=1;}
if (ok==0)return 0;
ok=0;
for (q=1;q<=9;q++)
if (!pus[q])
if (s[mid3][n]-s[mid3][mid2]-s[i][n]+s[i][mid2]==z[q]){ok=1;pus[q]=1;}
if (ok==0)return 0;
ok=0;
for (q=1;q<=9;q++)
if (!pus[q])
if (s[n][mid]-s[mid3][mid]==z[q]){ok=1;pus[q]=1;}
if (ok==0)return 0;
ok=0;
for (q=1;q<=9;q++)
if (!pus[q])
if (s[n][mid2]-s[n][mid]-s[mid3][mid2]+s[mid3][mid]==z[q]){ok=1;pus[q]=1;}
if (ok==0)return 0;
ok=0;
for (q=1;q<=9;q++)
if (!pus[q])
if (s[n][n]-s[n][mid2]-s[mid3][n]+s[mid3][mid2]==z[q]){ok=1;pus[q]=1;}
if (ok==0)return 0;
else {
printf("%ld %ld %ld %ld\n",i,mid3,mid,mid2);
return 1;
}
}
int verificare(){
for (t=1;t<=9;t++)
if (t!=j&&t!=k&&t!=r){
low3=i+1;
high3=n-1;
while (low3<=high3){
mid3=(low3+high3)/2;
if (s[mid3][mid]-s[i][mid]<z[t])
low3=mid3+1;
else if (s[mid3][mid]-s[i][mid]>z[t])
high3=mid3-1;
else if (afisare())return 1;
else break;
}
}
return 0;
}
int main(){
freopen("zone.in","r",stdin);
freopen("zone.out","w",stdout);
scanf("%ld",&n);
for (i=1;i<=9;i++)
scanf("%ld",&z[i]);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++){
scanf("%ld",&a);
s[i][j]=s[i-1][j]-s[i-1][j-1]+s[i][j-1]+a;
}
for (i=1;i<=n-2;i++)
for (j=1;j<=9;j++){
low=1;
high=n-2;
while (low<=high){
mid=(low+high)/2;
if (s[i][mid]<z[j])
low=mid+1;
else
if (s[i][mid]>z[j])
high=mid-1;
else{
for (k=1;k<=9;k++)
if (k!=j){
low2=mid+1;
high2=n-1;
while (low2<=high2){
mid2=(low2+high2)/2;
if (s[i][mid2]-s[i][mid]<z[k])
low2=mid2+1;
else
if (s[i][mid2]-s[i][mid]>z[k])
high2=mid2-1;
else{
for (r=1;r<=9;r++)
if (r!=k&&r!=j&&s[i][n]-s[i][mid2]==z[r])
if (verificare())return 0;
break;
}
}
}
break;
}
}
}
return 0;
}