Cod sursa(job #1237064)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 3 octombrie 2014 01:47:18
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,v[10],vv[10],x[600][600],s[600][600],i,j,a,ok,ii,jj,k,p,u,mid,nr;
FILE *f,*g;
int sum(int a,int b,int x,int y){
    return s[x][y]+s[a-1][b-1]-s[x][b-1]-s[a-1][y];
}
int main(){
    f=fopen("zone.in","r");
    g=fopen("zone.out","w");
    fscanf(f,"%d",&n);
    for(i=1;i<=9;i++){
        fscanf(f,"%d",&v[i]);
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            fscanf(f,"%d",&x[i][j]);
        }
    }
    s[1][1]=x[1][1];
    for(i=2;i<=n;i++){
        s[1][i]=s[1][i-1]+x[1][i];
        s[i][1]=s[i-1][1]+x[i][1];
    }
    for(i=2;i<=n;i++){
        for(j=2;j<=n;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x[i][j];
        }
    }
    for(i=1;i<n-1;i++){
        for(j=1;j<n-1;j++){
            ok=0;
            a=sum(1,1,i,j);
            for(k=1;k<=9;k++){
                if(v[k]==a){
                    ok=1;
                    break;
                }
            }
            if(ok==1){
                ok=0;
                for(ii=i+1;ii<n;ii++){
                    a=sum(i+1,1,ii,j);
                    for(k=1;k<=9;k++){
                        if(v[k]==a){
                            ok=1;
                            break;
                        }
                    }
                    if(ok==1){
                        for(jj=j+1;jj<n;jj++){
                            vv[1]=sum(1,1,i,j);
                            vv[2]=sum(1,j+1,i,jj);
                            vv[3]=sum(1,jj+1,i,n);
                            vv[4]=sum(i+1,1,ii,j);
                            vv[5]=sum(i+1,j+1,ii,jj);
                            vv[6]=sum(i+1,jj+1,ii,n);
                            vv[7]=sum(ii+1,1,n,j);
                            vv[8]=sum(ii+1,j+1,n,jj);
                            vv[9]=sum(ii+1,jj+1,n,n);
                            ok=1;
                            sort(v+1,v+10);
                            sort(vv+1,vv+10);
                            for(k=1;k<=9;k++){
                                if(v[k]!=vv[k]){
                                    ok=0;
                                    break;
                                }
                            }
                            if(ok==1){
                                fprintf(g,"%d %d %d %d",i,ii,j,jj);
                                return 0;
                            }
                        }
                    }
                }
            }
        }
    }









    fclose(f);
    fclose(g);
    return 0;
}