Pagini recente » Cod sursa (job #1896965) | Cod sursa (job #1976740) | Cod sursa (job #3190636) | Cod sursa (job #1723783) | Cod sursa (job #506098)
Cod sursa(job #506098)
#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;
if ((X<modX) && (Y<modY)) 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));
if ((X>=modX) || (Y>=modY))
{
FREQ[0] = N*N-1;
FREQ[1] = 1;
return;
}
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 tratat 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";
}