Cod sursa(job #506097)

Utilizator dcm9000Dinu Cristian Mircea - UPB dcm9000 Data 5 decembrie 2010 02:52:28
Problema Robotei Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <iostream>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <string>

using namespace std;

#define FILE_IN "robotei.in"
#define FILE_OUT "robotei.out"

#define INFY -1
#define UNK -2

int N, M, X, Y, modX, modY, offsetX, offsetY;

int FREQ[1000000];
int DIST[1000][1000];

int PERIOD;

#define nextX(x) (((x)*(x)+offsetX)%modX)
#define nextY(x) (((x)*(x)+offsetY)%modY)

void calcDist_r(int x, int y)
{
	if (DIST[x][y] != UNK) return;

	DIST[x][y] = INFY;

	int nx = nextX(x);
	int ny = nextY(y);
	calcDist_r(nx,ny);
	int remDist = DIST[nx][ny];

	if (remDist == INFY) return;

	DIST[x][y] = 1+remDist;
}

void calcDist()
{
	for (int x=0; x<modX; x++)
		for (int y=0; y<modY; y++)
			DIST[x][y] = UNK;

	DIST[X][Y] = 0;

	for (int x=0; x<modX; x++)
		for (int y=0; y<modY; y++)
			calcDist_r(x,y);

	int remDist = DIST[nextX(X)][nextY(Y)];
	PERIOD = (remDist == INFY) ? INFY : 1+remDist;
}

void solve()
{
	memset(FREQ, 0, sizeof(int)*(M+2));

	int freq, remDist, timeTo;
	for (int x=0; x<modX; x++)
		for (int y=0; y<modY; y++)
		{
			int equivX = 1+((N-x-1)/modX);
			int equivY = 1+((N-y-1)/modY);
			int robots = equivX*equivY;

			if ((x==X) && (y==Y)) robots--; // robotul (X,Y) este trata special

			remDist = DIST[nextX(x)][nextY(y)];

			freq = 0;
			if (remDist != INFY)
			{
				timeTo = 1+remDist;

				if (timeTo <= M)
				{
					freq++;
					if (PERIOD != INFY) freq += (M-timeTo)/PERIOD;
				}
			}

			FREQ[freq] += robots;
		}

	// Calcul pentru (X,Y)
	remDist = DIST[nextX(X)][nextY(Y)];
	freq = 1;
	if (remDist != INFY)
	{
		timeTo = 1+remDist;

		if (timeTo <= M)
		{
			freq++;
			if (PERIOD != INFY) freq += (M-timeTo)/PERIOD;
		}
	}
	FREQ[freq]++;
}

int main()
{
	ifstream fisIn(FILE_IN);
	ofstream fisOut(FILE_OUT);
	
	fisIn >> N >> M >> X >> Y >> modX >> modY >> offsetX >> offsetY;

	calcDist();
	solve();

	for (int i=0; i<=M+1; i++)
		if (FREQ[i]) fisOut << i << " " << FREQ[i] << "\n";
}