Cod sursa(job #17875)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 17 februarie 2007 11:04:01
Problema Robotei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

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() {
	queue <pair <int, int> > Q;
	vector <pair <int, int> > :: iterator k;
	int tx, ty, stop, u, v;

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

	for (Q.push(MP(X, Y)); !Q.empty(); Q.pop()) {
		
		tx = Q.front().first;
		ty = Q.front().second;

		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 = D[tx][ty] + 1;
			
			if (D[u][v] == -1)
				D[u][v] = D[tx][ty] + 1,
				Q.push(MP(u, v));
		}
	}
}

void modeleaza() {
	int i, r;

	for (i = 0, r = 0; i < N; ++i, ++r) {
		if (r == modX) r = 0;
		++toX[r];
	}
	for (i = 0, r = 0; i < N; ++i, ++r) {
		if (r == modY) r = 0;
		++toY[r];
	}
}

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] - 1;
				} 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] - 1;
					else
						count[0] += toX[i] * toY[j] - 1;
				}
			else
				count[0] += 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;
}