Cod sursa(job #959325)

Utilizator primulDarie Sergiu primul Data 8 iunie 2013 11:27:22
Problema Robotei Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <fstream>
#include <queue>
using namespace std;
  
ifstream F("robotei.in");
ofstream G("robotei.out");
  
typedef struct{int x,y;} point;
  
point m_p(int x,int y)
{
    point out;
    out.x = x;
    out.y = y;
    return out;
}
  
const int Nmax = 1010;
const int Mmax = 666740;
  
int N,M,Mx,My,Ox,Oy,Cicle,X,Y;
int Go[Nmax][Nmax];
int A[Nmax][Nmax];
int Mark[Nmax][Nmax];
int Sol[Mmax];
  
int next_x(int x)
{
    return (x*x+Ox)%Mx;
}
  
int next_y(int y)
{
    return (y*y+Oy)%My;
}
  
int NX[Nmax];
int NY[Nmax];
  
int Find_cicle()
{
    int x=X,y=Y,Stop=Mx*My,i;
    x = NX[x];
    y = NY[y];
    for (i=1;i<Stop && !(x==X && y==Y);++i)
        x=NX[x],y=NY[y];
    if ( x != X || y != Y ) return M+1;
    return i;
}
  
int get_dist(int x,int y)
{
    if ( Mark[x][y] == 1 )
        return A[x][y];
    Mark[x][y] = 1;
    A[x][y] = get_dist( NX[x] , NY[y] );
    A[x][y] += ( A[x][y] != 0 );
    return A[x][y];
}
  
int main()
{
    F>>N>>M>>X>>Y;--N;
    F>>Mx>>My>>Ox>>Oy;
  
    for (int i=0;i<Mx;++i)
        for (int j=0;j<My;++j)
            Go[i][j]=( 1+(N-i)/Mx )*( 1+(N-j)/My );
  
    for (int i=0;i<Mx;++i) NX[i]=next_x(i);
    for (int i=0;i<My;++i) NY[i]=next_y(i);
    Cicle = Find_cicle();
  
    A[X][Y] = 1;
    Mark[X][Y] = 1;
    for (int i=0;i<Mx;++i)
        for (int j=0;j<My;++j)
            if ( Mark[i][j] == 0 )
                A[i][j] = get_dist(i,j);
  
    for (int i=0;i<Mx;++i)
        for (int j=0;j<My;++j)
            if ( A[i][j] > 0 )
            {
                --A[i][j];
                if ( A[i][j] > 0 && A[i][j] <= M )
                    A[i][j] = 1 + ( M - A[i][j] ) / Cicle;
            }
    A[X][Y] = 1 + M / Cicle;
  
    for (int i=0;i<Mx;++i)
        for (int j=0;j<My;++j)
            Sol[ A[i][j] ] += Go[i][j];
    Sol[ A[X][Y] ] -= Go[X][Y];
    Sol[ A[X][Y] ] += 1;
    Sol[ A[X][Y]-1 ] += Go[X][Y]-1;
  
    for (int i=0;i<=M;++i)
        if ( Sol[i] != 0 )
            G<<i<<' '<<Sol[i]<<'\n';
}