Cod sursa(job #2116587)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 27 ianuarie 2018 19:34:56
Problema Robotei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
# include <fstream>
# define MAT 1010
# define DIM 667732
# define INF 1000000000
using namespace std;
ifstream fin("robotei.in");
ofstream fout("robotei.out");
int Marcat[MAT][MAT],d[MAT][MAT],tr[MAT][MAT];
int sol[DIM],restX[MAT],restY[MAT],rX[MAT],rY[MAT];
int n,m,x,y,modX,modY,offsetX,offsetY,i,j,ii,jj,nr,val;
int newX(int x){
    return (x*x+offsetX)%modX;
}
int newY(int y){
    return (y*y+offsetY)%modY;
}
int main () {
    fin>>n>>m>>x>>y>>modX>>modY>>offsetX>>offsetY;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            d[i][j]=INF;
    d[x][y]=0;
    Marcat[x][y]=1;
    for(i=0;i<modX;i++)
        for(j=0;j<modY;j++){
            if(i<modX&&y<modY&&Marcat[i][j])
                continue;
            ii=i;
            jj=j;
            while(Marcat[ii][jj]==0){
                Marcat[ii][jj]=1;
                nr++;
                ii=newX(ii);
                jj=newY(jj);
            }
            val=d[ii][jj];
            ii=i;
            jj=j;
            while(nr){
                d[ii][jj]=val+nr;
                nr--;
                ii=newX(ii);
                jj=newY(jj);
            }
        }
    for(i=0;i<n;i++){
        restX[newX(i)]++;
        restY[newY(i)]++;
        if(i<modX)
            rX[newX(i)]++;
        if(i<modY)
            rY[newY(i)]++;
    }
    for(i=0;i<modX;i++)
        for(j=0;j<modY;j++){
            tr[i][j]=restX[i]*restY[j]-rX[i]*rY[j];
        }
    i=newX(x);
    j=newY(y);
    nr=1;
    while(i!=x||j!=y){
        nr++;
        i=newX(i);
        j=newY(j);
    }
    for(i=0;i<modX;i++)
        for(j=0;j<modY;j++){
            if(d[i][j]==INF||m>d[i][j]){
                sol[0]+=tr[i][j]+1;
            }
            sol[(m-d[i][j])/nr+1]++;
            sol[(m-1-d[i][j])/nr+1]+=tr[i][j];
        }
    for(i=1;i<=m;i++)
        if(sol[i])
            fout<<i<<" "<<sol[i]<<"\n";
    return 0;
}