Cod sursa(job #132030)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 4 februarie 2008 21:32:35
Problema Zone Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.65 kb
#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;
}