Cod sursa(job #1653614)

Utilizator TibixbAndrei Tiberiu Tibixb Data 16 martie 2016 12:31:56
Problema Robotei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<fstream>
#define inf 0x7f7f7f7f
using namespace std;
int n, m, x, y, modx, mody, offx, offy, i, j, countt[1005][1005], counttx[1005], countty[1005], dist[1005][1005], ncycle, vizite[1005][1005], sol[1000005];
ifstream in("robotei.in");
ofstream out("robotei.out");
int next_x(int x)
{
    return (x*x+offx)%modx;
};
int next_y(int y)
{
    return (y*y+offy)%mody;
};
void cycle_detection(int x, int y)
{
    dist[x][y]=-1;
    int nx=next_x(x);
    int ny=next_y(y);
    if(dist[nx][ny]==inf)
        cycle_detection(nx, ny);
    if(dist[nx][ny]!=-1)
        dist[x][y]=dist[nx][ny]+1;
}
int main()
{
    in>>n>>m>>x>>y>>modx>>mody>>offx>>offy;
    for(i=0; i<n; i++)
    {
        counttx[next_x(i)]++;
        countty[next_y(i)]++;
    }
    for(i=0; i<modx; i++)
    {
        for(j=0; j<mody; j++)
        {
            countt[i][j]=counttx[i]*countty[j];
            dist[i][j]=inf;
        }
    }
    dist[x][y]=0;
    for(i=0; i<modx; i++)
        for(j=0; j<mody; j++)
            if(dist[i][j]==inf)
                cycle_detection(i, j);
    ncycle=dist[next_x(x)][next_y(y)]+1;
    for(i=0; i<modx; i++)
    {
        for(j=0; j<mody; j++)
        {
            if(dist[i][j]!=-1 && dist[i][j]<m)
                vizite[i][j]=1+(ncycle>0?(m-1-dist[i][j])/ncycle:0);
            sol[vizite[i][j]]+=countt[i][j];
        }
    }
    sol[vizite[next_x(x)][next_y(y)]]--;
    sol[vizite[next_x(x)][next_y(y)]+1]++;
    for(i=0; i<=m; i++)
    {
        if(sol[i]!=0)
            out<<i<<" "<<sol[i]<<"\n";
    }
    return 0;
}