Pagini recente » Cod sursa (job #2733485) | Cod sursa (job #1058727) | Cod sursa (job #3274048) | Cod sursa (job #387366) | Cod sursa (job #6596)
Cod sursa(job #6596)
#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 init()
{
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;
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];
}
int main()
{
fin=fopen(infile,"r");
fscanf(fin,"%d %d %d %d %d %d %d %d",&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;
}
init();
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;
}