Pagini recente » Cod sursa (job #1155873) | Cod sursa (job #1553775) | Cod sursa (job #510902) | Cod sursa (job #2614675) | Cod sursa (job #1046200)
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
int n, m, X, Y, modX, modY, offsetX, offsetY;
int sol[667000];
int newX[1010], newY[1010];
int Next[1010][1010], dist[1010][1010], cycle_len;
vector <pii> GT[1010][1010];
queue <pii> Q;
bool Skip, uz[1010][1010];
inline void Read()
{
ifstream fin("robotei.in");
fin >> n >> m >> X >> Y >> modX >> modY >> offsetX >> offsetY;
fin.close();
if(X >= modX || Y >= modY)
{
if(X < n && Y <n)
{
sol[0] = n * n - 1;
sol[1] = 1;
}
else
sol[0] = n * n;
Skip = true;
}
}
inline int Code(int x, int y)
{
// codifica o pozitie
return x * modY + y;
}
inline pii Decode(int code)
{
// decodifica o pozitie
return make_pair(code / modY, code % modY);
}
inline void BuildGraph()
{
int i, j, x, y;
for(i = 0; i < 1000; ++i)
{
newX[i] = (i * i + offsetX) % modX;
newY[i] = (i * i + offsetY) % modY;
}
for(i = 0; i < modX; ++i)
{
for(j = 0; j < modY; ++j)
{
dist[i][j] = 1000000000;
// graful normal - fiecare nod are gradul de iesire 1
Next[i][j] = Code(newX[i], newY[j]);
// graful transpus
x = Decode(Next[i][j]).first;
y = Decode(Next[i][j]).second;
GT[x][y].push_back(make_pair(i, j));
}
}
}
inline void GetDistances()
{
// gaseste distantele de la fiecare pozitie la (X, Y)
pii now;
vector <pii>::iterator it;
dist[X][Y] = 0;
Q.push(make_pair(X, Y));
while(!Q.empty())
{
now = Q.front();
Q.pop();
uz[now.x][now.y] = false;
if(dist[now.x][now.y] > m)
continue;
for(it = GT[now.x][now.y].begin(); it != GT[now.x][now.y].end(); ++it)
{
if(dist[(*it).x][(*it).y] > dist[now.x][now.y] + 1)
{
dist[(*it).x][(*it).y] = dist[now.x][now.y] + 1;
if(!uz[(*it).x][(*it).y])
{
uz[(*it).x][(*it).y] = true;
Q.push(*it);
}
}
}
}
}
inline void GetCycleLength()
{
// gaseste lungimea ciclului din care face parte (X, Y)
int x = Decode(Next[X][Y]).x;
int y = Decode(Next[X][Y]).y;
cycle_len = dist[x][y] + 1;
}
inline void Solve()
{
int i, j, nr, robotei, x, y;
for(i = 0; i < modX; ++i)
{
for(j = 0; j < modY; ++j)
{
// iau in calcul doar punctele din dreptunghiul modX x modY
if(dist[i][j] <= m)
{
nr = (m - dist[i][j]) / cycle_len + 1;
sol[nr]++;
}
else
sol[0]++;
// iau in calcul doar punctele din afara dreptunghiului modX x modY
robotei = ((n - 1 - i) / modX + 1) * ((n - 1 - j) / modY + 1) - 1;
x = Decode(Next[i][j]).first;
y = Decode(Next[i][j]).second;
if(dist[x][y] + 1 <= m)
{
nr = (m - dist[x][y] - 1) / cycle_len + 1;
sol[nr] += robotei;
}
else
sol[0] += robotei;
}
}
}
inline void Write()
{
int i;
ofstream fout("robotei.out");
for(i = 0; i <= m; ++i)
if(sol[i])
fout << i << ' ' << sol[i] << "\n";
fout.close();
}
int main()
{
Read();
if(!Skip)
{
BuildGraph();
GetDistances();
GetCycleLength();
Solve();
}
Write();
return 0;
}