Nu aveti permisiuni pentru a descarca fisierul grader_test3.ok

Cod sursa(job #17882)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 17 februarie 2007 11:39:28
Problema Robotei Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 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], badX[NMAX], badY[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, u, v;

	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, tx, ty;

	for (i = 0; i < N; ++i) {
		next(tx = i, ty = i);
		++toX[tx]; ++toY[ty];
		if (i < modX) ++badX[tx];
		if (i < modY) ++badY[ty];
	}
}

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] - badX[i] * badY[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] - badX[i] * badY[j];
					else
						count[0] += toX[i] * toY[j] - badX[i] * badY[j];
				}
			else
				count[0] += 1 + toX[i] * toY[j] - badX[i] * badY[j];
//			printf("%d %d => D = %d tx = %d ty = %d\n", i, j, D[i][j], 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();

	if (X >= modX || Y >= modY) return 1;

	graf();

	BFS();

	robot();

	write();

	return 0;
}