Pagini recente » Cod sursa (job #1839311) | Cod sursa (job #1602463) | Cod sursa (job #1101171) | Cod sursa (job #1161460) | Cod sursa (job #842120)
Cod sursa(job #842120)
#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)];
}
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;
dist[x][y] = m+1;
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;
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;
}
void getPasses() {
if (qx >= modX || qy >= modY) {
ans[0] = n*n-1;
ans[1] = 1;
return;
}
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;
++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;
}