Cod sursa(job #23053)

Utilizator VmanDuta Vlad Vman Data 27 februarie 2007 23:00:18
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.54 kb
#include <stdio.h>
#include <string.h>

#define nmax 513

int l1,l2,c1,c2,n,i,j,k,st,dr,m,w[10],ll1,ll2,cc1,cc2;
long long t[nmax][nmax], z[10];

void update()
{
ll1=l1;
ll2=l2;
cc1=c1;
cc2=c2;
}

int main()
{
      freopen("zone.in","r",stdin);
      scanf("%d\n",&n);
      for (i=0;i<9;++i)
          scanf("%lld",&z[i]);
      scanf("\n");
      cc1=n+1;
      cc2=cc1;
      ll1=cc1;
      ll2=cc1;
      for (i=1;i<=n;++i)
	{
	  for (j=1;j<=n;++j)
	      {
	      scanf("%lld",&t[i][j]);
	      t[i][j]+=t[i-1][j]+t[i][j-1]-t[i-1][j-1];
	      }
	scanf("\n");
        }
      fclose(stdin);
      //fixez valoare pt zona 1
      for (i=0;i<9;++i)
          {
           //fixez linia pt zona 1
           for (l1=1;l1<n-1;++l1)
               {
                //caut binar coloana pt zona 1
                st=1;
                dr=n-2;
                while (st+1<dr)
                      {
                        m=(st+dr)/2;
                        if (t[l1][m]>z[i]) dr=m;
                           else st=m;
                      }
                if (t[l1][dr]==z[i]) c1=dr;
                   else if (t[l1][st]==z[i]) c1=st;
			else c1=n+1;
		if (c1!=n+1)
		//fixez valoarea pt zona 2
		for (j=0;j<9;++j)
		    if (i!=j)
		       {
		       //cautare binara c2
		       st=c1+1;
		       dr=n-1;
		       while (st+1<dr)
			     {
			     m=(st+dr)/2;
			     if (t[l1][m]-t[l1][c1]>z[j]) dr=m;
				else st=m;
			     }
		       if (t[l1][st]-t[l1][c1]==z[j]) c2=st;
			  else if(t[l1][dr]-t[l1][c1]==z[j]) c2=dr;
			       else c2=n+1;
		       if (c2!=n+1)
		       //fixez valoarea pt zona 4
		       for (k=0;k<9;++k)
			   if ((k!=i)&&(k!=j))
			      {
			       //cautare binara l2
			       st=l1+1;
			       dr=n-1;
			       while (st+1<dr)
				     {
				      m=(st+dr)/2;
				      if (t[m][c1]-t[l1][c1]>z[k]) dr=m;
					 else st=m;
				     }
			       if (t[st][c1]-t[l1][c1]==z[k]) l2=st;
				  else if (t[dr][c1]-t[l1][c1]==z[k]) l2=dr;
				       else l2=n+1;
			       if (l2!=n+1)
			       {
			       //verific celelalte 6 zone
			       memset(w,0,sizeof(w));
			       w[i]=1;
			       w[j]=1;
			       w[k]=1;
			       st=3;
                               //verific pt zona 3
                               for (m=0;m<9;++m)
                                   if ((t[l1][n]-t[l1][c2]==z[m])&&(w[m]==0))
                                      {
                                      w[m]=1;
                                      ++st;
                                      break;
                                      }
                               //verific pt zona 5
                               for (m=0;m<9;++m)
                                   if ((t[l2][c2]-t[l2][c1]-t[l1][c2]+t[l1][c1]==z[m])&&(w[m]==0))
                                      {
                                      w[m]=1;
                                      ++st;
                                      break;
                                      }
                               //verific pt zona 6
                               for (m=0;m<9;++m)
                                   if ((t[l2][n]-t[l2][c2]-t[l1][n]+t[l1][c2]==z[m])&&(w[m]==0))
                                      {
                                      w[m]=1;
                                      ++st;
                                      break;
                                      }
                              //verific pt zona 7
                               for (m=0;m<9;++m)
                                   if ((t[n][c1]-t[l2][c1]==z[m])&&(w[m]==0))
                                      {
				      w[m]=1;
				      ++st;
				      break;
				      }
			      //verific pt zona 8
			       for (m=0;m<9;++m)
				   if ((t[n][c2]-t[n][c1]-t[l2][c2]+t[l2][c1]==z[m])&&(w[m]==0))
				      {
				      w[m]=1;
				      ++st;
				      break;
				      }
			      //verific pt zona 9
			       for (m=0;m<9;++m)
				   if ((t[n][n]-t[n][c2]-t[l2][n]+t[l2][c2]==z[m])&&(w[m]==0))
				      {
				      w[m]=1;
				      ++st;
				      break;
				      }
			      if (st==9)
				 if (l1<ll1) update();
				    else if ((l1==ll1)&&(c1<cc1)) update();
					 else if ((l1==ll1)&&(c1==cc1)&&(l2<ll2)) update();
					      else if ((l1==ll1)&&(c1==cc1)&&(l2==ll2)&&(c2<cc2)) update();
                              }
			      }
		       }
	       }
	  }
      freopen("zone.out","w",stdout);
      printf("%d %d %d %d",ll1,ll2,cc1,cc2);
      fclose(stdout);
      return 0;
}