Cod sursa(job #17871)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 17 februarie 2007 10:37:16
Problema Robotei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>

using namespace std;

#define PB push_back
#define MP make_pair

const int NMAX = 1 << 20;
const int MMAX = 1024;
const int INF = 0x3f3f3f3f;

int N, M;
int X, Y, rev;
int modX, modY;
int offsetX, offsetY;
vector <pair <int, int> > G[MMAX][MMAX];
int toX[NMAX], toY[NMAX];
int count[NMAX];
int D[MMAX][MMAX];

void next(int &tx, int &ty) {
	tx = (tx * tx + offsetX) % modX;
	ty = (ty * ty + offsetY) % modY;
}

void read() {
	FILE *fin = fopen("robotei.in", "rt");

	fscanf(fin, " %d %d", &N, &M);

	fscanf(fin, " %d %d", &X, &Y);

	fscanf(fin, " %d %d", &modX, &modY);

	fscanf(fin, " %d %d", &offsetX, &offsetY);

	fclose(fin);
}

void graf() {
	int i, j, tx, ty;

	for (i = 0; i < modX; ++i)
		for (j = 0; j < modY; ++j) {
			next(tx = i, ty = j);
			G[tx][ty].PB(MP(i, j));
		}
}

void BFS() {
	deque <pair <int, int> > Q[2];
	deque <pair <int, int> > :: iterator j;
	vector <pair <int, int> > :: iterator k;
	int i, tx, ty, stop, u, v;

	stop = modX * modY;
	memset(D, 0xff, sizeof(D));
	rev = -1;

	Q[0].PB(MP(X, Y));
	for (i = 0; !Q[i & 1].empty(); ++i) {
		
		for (j = Q[i & 1].begin(); j != Q[i & 1].end(); ++j) {
			tx = j->first;
			ty = j->second;


			if (D[tx][ty] == -1) {
				D[tx][ty] = i;

				for (k = G[tx][ty].begin(); k != G[tx][ty].end(); ++k) {
					u = k->first; v = k->second;

					if (rev == -1 && u == X && v == Y) rev = i + 1;

					if (D[u][v] == -1)
						Q[(i + 1) & 1].PB(MP(u, v));
				}
			}
		}

		Q[i & 1].clear();
	}
}

void modeleaza() {
	int i;

	for (i = 0; i < N; ++i) 
		toX[i] = i < modX ? i : toX[i - modX],
		toY[i] = i < modY ? i : toY[i - modY];
}

void robot() {
	int i, j;
	
	modeleaza();

	for (i = 0; i < modX; ++i)
		for (j = 0; j < modY; ++j) 
			if (D[i][j] != -1)
				if (rev == -1) {
					++count[M >= D[i][j]];
					count[M >= D[i][j] + 1] += toX[i] * toY[j];
				} else {
					if (M >= D[i][j]) 
						++count[1 + (M - D[i][j]) / rev]; 
					else 
						++count[0];

					if (M >= D[i][j] + 1)
						count[1 + (M - D[i][j] - 1) / rev] += toX[i] * toY[j];
					else
						count[0] += toX[i] * toY[j];
				}
			else
				count[0] += 1 + toX[i] * toY[j];
}

void write() {
	FILE *fout = fopen("robotei.out", "wt");
	int i;

	for (i = 0; i <= M; ++i)
		if (count[i])
			fprintf(fout, "%d %d\n", i, count[i]);

	fclose(fout);
}

int main() {

	read();

	graf();

	BFS();

	robot();

	write();

	return 0;
}