Cod sursa(job #482906)

Utilizator razvi9Jurca Razvan razvi9 Data 6 septembrie 2010 00:19:56
Problema Robotei Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

vector<pair<int, int> > a[1001][1001];
char viz[1001][1001];
int c[1001][1001];
int sol[1000000];
int n, M, x, y, modx, mody, dx, dy, lg;

inline int newX(int x)
{
	return (x * x + dx) % modx;
}

inline int newY(int y)
{
	return (y * y + dy) % mody;
}

void solve()
{
	int n, m, i, j;
	n = modx;
	m = mody;
	for(i=0;i<n;++i)
		for(j=0;j<m;++j)
			a[newX(i)][newY(j)].push_back(make_pair(i, j));

	queue<pair<int, int> > q;
	q.push(make_pair(x, y));
	viz[x][y] = 1;
	int len = 0;
	int count = 1, newCount;

	while(count && len <= M)
	{
		for(newCount = 0;count;--count)
		{
			pair<int, int> p = q.front(); q.pop();
			sol[(M - len) / lg + 1] += c[p.first][p.second];

			for(vector<pair<int, int> >::iterator it = a[p.first][p.second].begin(); it != a[p.first][p.second].end(); ++ it)
				if(!viz[it->first][it->second])
				{
					viz[it->first][it->second] = 1;
					q.push(make_pair(it->first, it->second)),
					++ newCount;
				}
		}

		count = newCount;
		++ len;
	}

	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			if(!viz[i][j])
				sol[0] += c[i][j];
}

int main()
{
	ifstream cin("robotei.in");
	ofstream cout("robotei.out");

	cin >> n >> M >> x >> y >> modx >> mody >> dx >> dy;

	x = x % modx;
	y = y % mody;
	dx %= modx;
	dy %= mody;

	int xi = x,
		yi = y;
	lg = 0;

	do
	{
		xi = newX(xi);
		yi = newY(yi);
		++ lg;
	}while((xi != x || yi != y) && lg <= M);

	for(int i=0;i<modx;++i)
	{
		int vi = (n - i + modx - 1) / modx;
		for(int j=0;j<mody;++j)
			c[i][j] = vi * ((n - j + mody - 1) / mody);
	}

	solve();

	for(int i=0;i<=M;++i)
		if(sol[i])
			cout << i << " " << sol[i] << "\n";

	return 0;
}