Pagini recente » Cod sursa (job #635949) | Cod sursa (job #1388114) | Cod sursa (job #2531323) | Cod sursa (job #1168386) | Cod sursa (job #851867)
Cod sursa(job #851867)
#include<fstream>
#define DIM 550
using namespace std;
ifstream f("zone.in");
ofstream g("zone.out");
int n;
int c1,c2,l1,l2,ok_t;
int N[20],V[DIM][DIM],Fr[20];
void read(){
int i,j;
f>>n;
for(i=1;i<=9;i++)
f>>N[i];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
f>>V[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
V[i][j]+=(V[i-1][j]+V[i][j-1]-V[i-1][j-1]);
}
int validate(){
int sum1=V[l2][c2]-V[l2][c1]-V[l1][c2]+V[l1][c1];
int sum2=V[l2][n]-V[l2][c2]-V[l1][n]+V[l1][c2];
int sum3=V[n][c2]-V[n][c1]-V[l2][c2]+V[l2][c1];
int sum4=V[n][n]-V[n][c2]-V[l2][n]+V[l2][c2];
int i,ok1,ok2,ok3,ok4;
for(i=1;i<=9;i++){
if(Fr[i]==0&&N[i]==sum1){
ok1=1;Fr[i]=1;break;
}
}
for(i=1;i<=9;i++){
if(Fr[i]==0&&N[i]==sum2){
ok2=1;Fr[i]=1;break;
}
}
for(i=1;i<=9;i++){
if(Fr[i]==0&&N[i]==sum3){
ok3=1;Fr[i]=1;break;
}
}
for(i=1;i<=9;i++){
if(Fr[i]==0&&N[i]==sum4){
ok4=1;Fr[i]=1;break;
}
}
return ok1&&ok2&&ok3&&ok4;
}
void find_l2(){
int sum_t=V[n][c1]-V[l1][c1];
int sum1,sum2;
int i,j,st,dr,mid,ok=1;
for(i=1;i<=9;i++){
if(Fr[i]==0){
Fr[i]=1;
sum1=N[i];
st=l1+1;dr=n-1;
while(st<=dr&&ok){
mid=(st+dr)/2;
sum2=V[mid][c1]-V[l1][c1];
if(sum2==sum1){
for(j=1;j<=9;j++)
if(Fr[j]==0&&(N[j]==sum_t-sum2)){
Fr[j]=1;l2=mid;
if(validate()){
g<<l1<<" "<<l2<<" "<<c1<<" "<<c2;
ok_t=1;
return;
}
ok=0;
Fr[j]=0;
break;
}
}
else{
if(sum2>sum1)
dr=mid-1;
else
st=mid+1;
}
}
Fr[i]=0;
}
}
}
void find_c2(){
int sum_t=V[l1][n]-V[l1][c1];
int sum1,sum2;
int i,j,st,dr,mid,ok=1;
for(i=1;i<=9;i++){
if(Fr[i]==0){
Fr[i]=1;
sum1=N[i];
st=c1+1;dr=n-1;
while(st<=dr&&ok){
mid=(st+dr)/2;
sum2=V[l1][mid]-V[l1][c1];
if(sum2==sum1){
for(j=1;j<=9;j++)
if(Fr[j]==0&&N[j]==(sum_t-sum1)){
Fr[j]=1;
c2=mid;
find_l2();
if(ok_t)
return;
ok=0;
Fr[j]=0;
break;
}
}
else{
if(sum2>sum1)
dr=mid-1;
else
st=mid+1;
}
}
Fr[i]=0;
}
}
}
void find_c1(){
int st,dr;
int mid,sum;
for(int i=1;i<=9;i++){
Fr[i]=1;
sum=N[i];st=1;dr=n-1;
while(st<=dr){
mid=(st+dr)/2;
if(V[l1][mid]==sum){
c1=mid;
find_c2();
if(ok_t)
return;
break;
}
else{
if(V[l1][mid]>sum)
dr=mid-1;
else
st=mid+1;
}
}
Fr[i]=0;
}
}
int main(){
read();
for(l1=1;l1<n&&(ok_t==0);l1++)
find_c1();
return 0;
}