Cod sursa(job #553384)

Utilizator tvladTataranu Vlad tvlad Data 13 martie 2011 23:04:39
Problema Robotei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int XY_MAX = 1000;
const int M_MAX = 666733;

int n, m, modX, modY, offX, offY;
int stepInX[XY_MAX], stepInY[XY_MAX];
int stepOutX[XY_MAX], stepOutY[XY_MAX];
int qx, qy;
int cycle;
int dist[XY_MAX][XY_MAX];
int ans[M_MAX];

inline int nextX ( int x ) { return (int)(((long long)x*x + offX) % modX); }
inline int nextY ( int y ) { return (int)(((long long)y*y + offY) % modY); }

void pack() {
	for (int x = 0; x < modX; ++x)
		++stepInX[nextX(x)];
	for (int y = 0; y < modY; ++y)
		++stepInY[nextY(y)];
	for (int x = modX; x < n; ++x)
		++stepOutX[nextX(x)];
	for (int y = modY; y < n; ++y)
		++stepOutY[nextY(y)];

/*	for (int i = 0; i < modX; ++i)
		cerr << '(' << stepInX[i] << ','<< stepOutX[i] << ") ";
	cerr << '\n';
	for (int i = 0; i < modY; ++i)
		cerr << '(' << stepInY[i] << ','<< stepOutY[i] << ") ";
	cerr << '\n';*/
}

inline int outOfRange ( int x, int y ) { return stepInX[x] * stepOutY[y] + stepOutX[x] * stepInY[y] + stepOutX[x] * stepOutY[y]; }

int getPointDistance ( int x, int y ) {
	if (x == qx && y == qy)
		return dist[x][y] = 0;
//	cerr << "Get PD " << x << ", " << y << "\n";
	int nx = nextX(x);
	int ny = nextY(y);
	if (dist[nx][ny] != 0 || (x == qx && y == qy))
		dist[x][y] = dist[nx][ny] + 1; else
		dist[x][y] = getPointDistance(nx, ny) + 1;
//	cerr << "(" << x << "," << y << ") - " << dist[x][y] << '\n';
	return dist[x][y];
}

void getAllDistances() {
	for (int x = 0; x < modX; ++x)
		for (int y = 0; y < modY; ++y)
			if (dist[x][y] == 0 && (x != qx || y != qy))
				getPointDistance(x, y);
	cycle = dist[nextX(qx)][nextY(qy)] + 1;
	
/*	for (int x = 0; x < modX; ++x) {
		for (int y = 0; y < modY; ++y)
			cerr << dist[x][y] << ' ';
		cerr << '\n';
	}
	cerr << "Cycle = " << cycle << '\n';*/
}

void getPasses() {
	for (int x = 0; x < modX; ++x) {
		for (int y = 0; y < modY; ++y) {
			int passes = 0, plus = 0;
			if (dist[x][y] <= m)
				passes = 1 + (m - dist[x][y]) / cycle;
			if (dist[x][y] < m)
				plus = 1 + (m - dist[x][y] - 1) / cycle;
//			cerr << "(" << x << "," << y << ") passed " << passes << " times\n" << outOfRange(x,y) << " more passed " << plus << " times\n";
			++ans[passes];
			ans[plus] += outOfRange(x,y);
		}
	}
}

int main() {
	ifstream fin("robotei.in");
	ofstream fout("robotei.out");
	
	fin >> n >> m >> qx >> qy >> modX >> modY >> offX >> offY;
	
/*	pack();
	getAllDistances();
	getPasses();*/

	for (int i = 0; i <= m; ++i)
		if (ans[i] > 0)
			fout << i << ' ' << ans[i] << '\n';

	return 0;
}