Pagini recente » Cod sursa (job #745437) | Cod sursa (job #2570689) | Cod sursa (job #1759559) | Cod sursa (job #3283421) | Cod sursa (job #3247180)
// Ilie "The-Winner" Dumitru
#include<cstdio>
const int NMAX=1024, MMAX=700000;
int N, M, modX, modY, offX, offY, tarX, tarY;
bool vis[NMAX][NMAX];
long long time[NMAX][NMAX], cnt[NMAX][NMAX];
long long period;
long long answers[MMAX];
int dfs(int x, int y)
{
if(x==tarX && y==tarY)
return 0;
if(vis[x][y])
return time[x][y];
vis[x][y]=1;
time[x][y]=-1;
int aux=dfs((x*x+offX)%modX, (y*y+offY)%modY);
if(aux!=-1)
time[x][y]=aux+1;
return time[x][y];
}
void update(int x, int y)
{
if(time[x][y]==-1 || time[x][y]>M)
{
answers[0]+=cnt[x][y];
return;
}
if(x==tarX && y==tarY)
{
if(period==-1)
{
++answers[1];
answers[0]+=cnt[x][y]-1;
return;
}
answers[M/period+1]+=1;
int c=cnt[x][y]-1;
x=(x*x+offX)%modX;
y=(y*y+offY)%modY;
int passes=0, left=M-1;
if(time[x][y]>left)
{
answers[0]+=c;
return;
}
left-=time[x][y];
++passes;
passes+=left/period;
answers[passes]+=c;
}
else
{
if(period==-1)
{
answers[1]+=cnt[x][y];
return;
}
int passes=0, left=M;
left-=time[x][y];
++passes;
passes+=left/period;
answers[passes]+=cnt[x][y];
}
}
int main()
{
FILE* f=fopen("robotei.in", "r"), *g=fopen("robotei.out", "w");
int i, j;
fscanf(f, "%d%d%d%d%d%d%d%d", &N, &M, &tarX, &tarY, &modX, &modY, &offX, &offY);
for(i=0;i<modX;++i)
for(j=0;j<modY;++j)
{
if(!vis[i][j])
dfs(i, j);
cnt[i][j]=(N/modX+(N%modX>i))*(N/modY+(N%modY>j));
}
if(time[(tarX*tarX+offX)%modX][(tarY*tarY+offY)%modY]==-1)
period=-1;
else
period=time[(tarX*tarX+offX)%modX][(tarY*tarY+offY)%modY]+1;
for(i=0;i<modX;++i)
for(j=0;j<modY;++j)
update(i, j);
for(i=0;i<=M;++i)
if(answers[i])
fprintf(g, "%d %lld\n", i, answers[i]);
fclose(f);
fclose(g);
return 0;
}