Pagini recente » Clasament preoni6a | Cod sursa (job #2794098) | Cod sursa (job #2007707) | Cod sursa (job #1685633) | Cod sursa (job #1144170)
#include <fstream>
#include <cstring>
#include <vector>
#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 = 666741;
int N,M,Mx,My,Ox,Oy,Cicle,X,Y;
vector<point> V[Nmax][Nmax];
int Go[Nmax][Nmax];
int A[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;
}
#define IT(type) vector<type>::iterator
void BFS(int x,int y)
{
queue<point> Q;
Q.push(m_p(x,y));
A[x][y] = 1;
while ( Q.size() )
{
point nod = Q.front();
Q.pop();
for (IT(point) it=V[nod.x][nod.y].begin();it!=V[nod.x][nod.y].end();++it)
if ( A[it->x][it->y] == 0 )
{
A[it->x][it->y] = A[nod.x][nod.y]+1;
Q.push( *it );
}
}
}
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();
for (int i=0;i<Mx;++i)
for (int j=0;j<My;++j)
V[NX[i]][NY[j]].push_back(m_p(i,j));
BFS(X,Y);
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';
}