Cod sursa(job #6635)

Utilizator stef2nStefan Istrate stef2n Data 20 ianuarie 2007 13:36:04
Problema Robotei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.18 kb
#include <stdio.h>

#define infile "robotei.in"
#define outfile "robotei.out"
#define DMAX 1005

FILE *fin,*fout;
long long N,M,X,Y,modX,modY,offsetX,offsetY;
int countX[DMAX],countY[DMAX];
long long count[DMAX][DMAX]; // cate elemente ajung in pozitia (lin,col) dupa o singura mutare
int dist[DMAX][DMAX]; // distanta de la pozitia (lin,col) la pozitia (X,Y)
long long sol[1000005];

inline int new_x(int x)
  {
   return ((long long)x*(long long)x+offsetX)%(long long)modX;
  }

inline int new_y(int y)
  {
   return ((long long)y*(long long)y+offsetY)%(long long)modY;
  }

void ciclu(int x, int y)
  {
   int newx=new_x(x);
   int newy=new_y(y);
   if(newx==X && newy==Y)
     {
      dist[x][y]=1;
      return;
     }
   if(dist[newx][newy]==0)
     return;
   dist[newx][newy]=0;
   ciclu(newx,newy);
   if(!dist[newx][newy])
     dist[x][y]=0;
   else
     dist[x][y]=dist[newx][newy]+1;
  }

void conexiune(int x, int y)
  {
   int newx=new_x(x);
   int newy=new_y(y);
   if(newx==X && newy==Y)
     {
      dist[x][y]=1;
      return;
     }
   if(dist[newx][newy]==0)
     return;
   if(dist[newx][newy]>0)
     {
      dist[x][y]=dist[newx][newy]+1;
      return;
     }
   // dist[newx][newy]==-1
   dist[newx][newy]=0;
   conexiune(newx,newy);
   if(!dist[newx][newy])
     dist[x][y]=0;
   else
     dist[x][y]=dist[newx][newy]+1;
  }

void solve()
  {
   int i,j;
   for(i=0;i<modX;i++)
      countX[i]=0;
   for(i=0;i<N;i++)
      countX[((long long)i*(long long)i)%(long long)modX]++;
   for(i=0;i<modY;i++)
      countY[i]=0;
   for(i=0;i<N;i++)
      countY[((long long)i*(long long)i)%(long long)modY]++;
   for(i=0;i<modX;i++)
      for(j=0;j<modY;j++)
         {
          int ind1=(i-offsetX)%modX;
          if(ind1<0)
            ind1+=modX;
          int ind2=(j-offsetY)%modY;
          if(ind2<0)
            ind2+=modY;
          count[i][j]=countX[ind1]*(long long)countY[ind2];
         }
   for(i=0;i<modX;i++)
      for(j=0;j<modY;j++)
         dist[i][j]=-1;
   dist[X][Y]=0;
   ciclu(X,Y);
   for(i=0;i<modX;i++)
      for(j=0;j<modY;j++)
         if(dist[i][j]==-1)
           {
            dist[i][j]=0;
            conexiune(i,j);
           }

   int ramase,newx,newy;
   newx=new_x(X);
   newy=new_y(Y);
   for(i=0;i<=M;i++)
      sol[i]=0;
   // FROM HERE /////////////////////////////////////////////////////////////////////////
   for(i=0;i<modX;i++)
      for(j=0;j<modY;j++)
         if(dist[i][j])
           if((i!=X || j!=Y) && (i!=newx || j!=newy))
             {
              ramase=M-dist[i][j]-1;
              if(ramase>=0)
                if(dist[X][Y]>0)
                  sol[ramase/dist[X][Y]+1]+=count[i][j];
                else
                  sol[1]+=count[i][j];
             }
           else
             if(newx==X && newy==Y)
               {
                ramase=M-1;
                if(ramase>=0)
                  {sol[ramase+1]+=count[X][Y]-1;
                   sol[ramase+2]++;}
               }
             else
               if(i==X && j==Y)
                 {
                  ramase=M-1;
                  if(ramase>=0)
                    if(dist[X][Y]>0)
                      sol[ramase/dist[X][Y]+1]+=count[X][Y];
                    else
                      sol[1]+=count[X][Y];
                 }
               else // sunt in pozitia (newx,newy)
                 {
                  ramase=M-dist[newx][newy]-1;
                  if(ramase>=0)
                    {sol[ramase/dist[X][Y]+1]+=count[newx][newy]-1;
                     sol[ramase/dist[X][Y]+2]++;}
                  else
                    sol[1]+=count[X][Y];
                 }
         else
           if(i==X && j==Y)
             sol[1]+=count[X][Y];
           else
             if(i==newx && j==newy)
               sol[1]++;
   // TO HERE /////////////////////////////////////////////////////////////////////////
  }


int main()
{
fin=fopen(infile,"r");
fscanf(fin,"%Ld %Ld %Ld %Ld %Ld %Ld %Ld %Ld",&N,&M,&X,&Y,&modX,&modY,&offsetX,&offsetY);
fclose(fin);
if(X>=modX || Y>=modY)
  {
   fout=fopen(outfile,"w");
   fprintf(fout,"1 1\n");
   fclose(fout);
   return 0;
  }
solve();
fout=fopen(outfile,"w");
for(int i=1;i<=M;i++)
   if(sol[i])
     fprintf(fout,"%d %Ld\n",i,sol[i]);
fclose(fout);
return 0;
}