Cod sursa(job #605893)

Utilizator crushackPopescu Silviu crushack Data 2 august 2011 18:13:45
Problema Robotei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>
#include <assert.h>
#define INF 0x3f3f3f3f
#define NMax 1010
#define MMax 500010
const char IN[]="robotei.in",OUT[]="robotei.out";

int N,M,X,Y,modX,modY,offsetX,offsetY;
int T[NMax][NMax];
int Sol[MMax];

void next(int &X,int &Y){
    X= (X*X+offsetX)%modX;
    Y= (Y*Y+offsetY)%modY;
}

int go(int x,int y)
{
    if  (T[x][y] && T[x][y]!=-1) {
        if (x==X && y==Y) return 0;
        return T[x][y];
    }
    if  (T[x][y]==-1)
    {
         T[x][y]=INF;
         if (x==X && y==Y) T[x][y]=0;
         return T[x][y];
    }
    int nx=x,ny=y;
    T[x][y]=-1;
    next(nx,ny);
    T[x][y]=go(nx,ny)+1;
    return T[x][y];
}

void solve()
{
    int i,j,x,y,v,m;

    go(X,Y);
    for (i=0;i<modX;++i)
        for (j=0;j<modY;++j) if (!T[i][j])
            go(i,j);
    for (i=0;i<N;++i)
        for (j=0;j<N;++j)
        {
            x=i;y=j;v=0;m=M;
            next(x,y);
            if (i==X && j==Y) ++v;
            if (x==X && y==Y && m>=1) ++v,--m;
            else
            {
                if (T[x][y]+1<=m) ++v;
                m-= T[x][y]+1;
            }
            if (T[X][Y]) v+= m/T[X][Y];
            ++Sol[v];
        }
}

int main()
{
    freopen(IN,"r",stdin);
    scanf("%d%d%d%d%d%d%d%d",&N,&M,&X,&Y,&modX,&modY,&offsetX,&offsetY);
    fclose(stdin);

    solve();

    freopen(OUT,"w",stdout);
    for (int i=0;i<=M;++i) if (Sol[i])
        printf("%d %d\n",i,Sol[i]);
    fclose(stdout);

    return 0;
}