Cod sursa(job #17902)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 17 februarie 2007 12:44:22
Problema Robotei Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define MAXN 1002
#define MAXM 667000

int N, M, X, Y, modX, modY, dx, dy;
int C, nr[MAXM];

int nrX[MAXN], nrY[MAXN];

int dist[MAXN][MAXN];
vector< pair<int, int> > con[MAXN][MAXN];
queue< pair<int, int> > Q;


inline void move( int X, int Y, int &nX, int &nY )
{
	nX = (X * X + dx) % modX;
	nY = (Y * Y + dy) % modY;
}

inline int calculate( int X, int Y )
{
	if (dist[X][Y] == -1)
		return 0;

	int _M = M - dist[X][Y];
	if (C == -1)
		return 1;
	return (_M / C) + 1;
}

int main()
{
	freopen("robotei.in", "rt", stdin);
	freopen("robotei.out", "wt", stdout);
	scanf("%d %d %d %d %d %d %d %d", &N, &M, &X, &Y, &modX, &modY, &dx, &dy);
	dx %= modX; dy %= modY;

	if (X >= modX || Y >= modY)
	{
		printf("0 %d\n1 1\n", N * N - 1);
		return 0;
	}

	int nX, nY, i;
	nX = X; nY = Y; C = -1;
	for (i = 1; i <= modX * modY; i++)
	{
		move( nX, nY, nX, nY );
		if (nX == X && nY == Y)		//lungimea ciclului care contine (X, Y)
		{
			C = i;
			break;
		}
	}

	int j;
	for (i = 0; i < modX; i++)
		for (j = 0; j < modY; j++)
		{
			move( i, j, nX, nY );
			con[ nX ][ nY ].push_back( make_pair(i, j) );
			dist[i][j] = -1;
		}

	for (dist[X][Y] = 0, Q.push( make_pair(X, Y) ); !Q.empty(); Q.pop())
	{
		int x = Q.front().first, y = Q.front().second;
		vector< pair<int, int> > :: iterator it;
		for (it = con[x][y].begin(); it != con[x][y].end(); it++)
		{
			nX = (*it).first;
			nY = (*it).second;
			if (dist[nX][nY] != -1)
				continue;

			dist[nX][nY] = dist[x][y] + 1;
			Q.push( make_pair(nX, nY) );
		}
	}

	for (i = 0; i < modX; i++)
		for (j = 0; j < modY; j++)
		{
			int k = calculate(i, j);
			nr[k]++;
		}

	M--;
	for (i = 0; i < modX; i++)
	{
		//trebuie sa calculez cate nr din intervalu [0, N - 1]
		//respecta conditia (a * a + dx) % modX == i.
		nrX[i] = 0;
		for (j = 0; j < N; j++)
		{
			if ( (j * j + dx) % modX != i )
				continue;
			nrX[i]++;
		}
	}

	for (i = 0; i < modY; i++)
	{
		//trebuie sa calculez cate nr din intervalu [0, N - 1]
		//respecta conditia (a * a + dy) % modY == i.
		nrY[i] = 0;
		for (j = 0; j < N; j++)
		{
			if ( (j * j + dy) % modY != i )
				continue;
			nrY[i]++;
		}
	}

	for (i = 0; i < modX; i++)
		for (j = 0; j < modY; j++)
		{
			int k = calculate(i, j);
			nr[k] += nrX[i] * nrY[j];

			move(i, j, nX, nY);			//am numarat si elementele care aveau ambele coordonate
			k = calculate(nX, nY);			//in intervalele [0..modX-1] si [0..modY-1]
			nr[k]--;				//trebuie scazute
		}
	
	for (i = 0; i <= M; i++)
		if (nr[i])
			printf("%d %d\n", i, nr[i]);
	return 0;
}