Cod sursa(job #2117381)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 28 ianuarie 2018 20:20:36
Problema Robotei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 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];
int n,m,x,y,modX,modY,offsetX,offsetY,i,j,ii,jj,nr,val,ok;
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<modX;i++)
        for(j=0;j<modY;j++)
            d[i][j]=INF;
    d[x][y]=0;
    Marcat[x][y]=1;
    for(i=0;i<n;i++){
        restX[newX(i)]++;
        restY[newY(i)]++;
    }
    tr[newX(x)][newY(y)]--;
    for(i=0;i<modX;i++)
        for(j=0;j<modY;j++)
            tr[i][j]+=restX[i]*restY[j];
    for(i=0;i<modX;i++)
        for(j=0;j<modY;j++){
            ii=i;
            jj=j;
            nr=0;
            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]=nr+val;
                nr--;
                ii=newX(ii);
                jj=newY(jj);
            }
        }
    nr=1;
    i=newX(x);
    j=newY(y);
    ok=1;
    while(i!=x||j!=y){
        nr++;
        if(nr>modX*modY){
            ok=0;
            break;
        }
        i=newX(i);
        j=newY(j);
    }
    if(ok){
        sol[m/nr+1]++;
        for(i=0;i<modX;i++)
            for(j=0;j<modY;j++){
                if(d[i][j]>m-1){
                    sol[0]+=tr[i][j];
                    continue;
                }
                sol[(m-1-d[i][j])/nr+1]+=tr[i][j];
            }
    }
    else{
        sol[1]++;
        for(i=0;i<modX;i++)
            for(j=0;j<modY;j++){
                if(d[i][j]>m-1){
                    sol[0]+=tr[i][j];
                    continue;
                }
                sol[1]+=tr[i][j];
            }
    }
    for(i=0;i<=m;i++)
        if(sol[i])
            fout<<i<<" "<<sol[i]<<"\n";
    return 0;
}