Cod sursa(job #553445)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 14 martie 2011 07:32:47
Problema Robotei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <stdio.h>
#include <vector>
#include <utility>

using namespace std;

#define pii 	pair <int, int>
#define maxK 	1010
#define maxN 	50000

vector <pii> prev[maxK][maxK];
int N, M, offsetX, offsetY, modX, modY, dist[maxK][maxK], Sol[maxN];
pii q[maxK * maxK], the_node;

inline pii next (pii now) {
	return make_pair((now.first * now.first + offsetX) % modX, (now.second * now.second + offsetY) % modY);
}

int dfs (pii node, int level = 0) {
//	fprintf(stderr, "%d %d | %d\n", node.first, node.second, level);
	if (level > modX * modY and node != the_node)
		return modX * modY;
	if (node == the_node and level != 0)
		return 0;
	return dfs (next(node), level + 1) + 1;
}

int main () {
	int i, j, X, Y, p, u, cycle_length, nrX, nrY, sol;
	pii _prev, _next, now;

	freopen("robotei.in", "r", stdin);
	freopen("robotei.out", "w", stdout);

	scanf("%d%d%d%d%d%d%d%d", &N, &M, &X, &Y, &modX, &modY, &offsetX, &offsetY);

	the_node = make_pair(X, Y);
	cycle_length = dfs (the_node);

	for (i = 0; i < modX; ++ i)
		for (j = 0; j < modY; ++ j) {
			_next = next(make_pair(i, j));
			prev[_next.first][_next.second].push_back(make_pair(i, j));
		}
	
	p = u = 0;
	q[u ++] = the_node;
	for (; p < u;) {
		now = q[p ++];
		for (i = 0; i < (int) prev[now.first][now.second].size(); ++ i) {
			_prev = prev[now.first][now.second][i];
			if (_prev != the_node && ! dist[_prev.first][_prev.second]) {
				dist[_prev.first][_prev.second] = dist[now.first][now.second] + 1;
				q[u ++] = _prev;
			}
		}
	}

	if (cycle_length > modX * modY) {
		printf("%d %d\n", 1, u - 1);
		for (i = 2; i <= N; ++ i)
			printf("%d %d\n", i, 0);
		return 0;
	}

	for (i = 0; i < modX; ++ i)
		for (j = 0; j < modY; ++ j) {
			nrX = N / modX + (i < N % modX);
			nrY = N / modY + (j < N % modY);

			if (dist[i][j] != 0) {
				sol = (M >= dist[i][j]) ? 1 + (M - dist[i][j]) / cycle_length : 0;
				Sol[sol] += nrX * nrY;
			} else if (i == the_node.first and j == the_node.second) {
				sol = 1 + M / cycle_length;
				Sol[sol] ++;
				Sol[sol - 1] += nrX * nrY - 1;
			} else {
			//	fprintf(stderr, "%d ", sol);
			}
//			fprintf(stderr, "%d ", sol);
		}

	for (i = 0; i <= M; ++ i)
		if (Sol[i])
			printf("%d %d\n", i, Sol[i]);
}