Cod sursa(job #3318035)

Utilizator Andrei1209Andrei Mircea Andrei1209 Data 26 octombrie 2025 17:14:54
Problema Robotei Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream fin("robotei.in");
ofstream fout("robotei.out");

const int dim = 1000;
int dist[dim + 5][dim + 5], fLin[dim + 5], fCol[dim + 5], rasp[1000005];
int n, m, modx, mody, offsetX, offsetY, x, y;

void reset()
{
    for (int i = 0; i < modx; ++i)
        for (int j = 0; j < mody; ++j)
            dist[i][j] = -1;
}

void calc(int i, int j)
{
    if (dist[i][j] != -1)
        return;

    int nxti = (i * i + offsetX) % modx;
    int nxtj = (j * j + offsetY) % mody;

    dist[i][j] = -2; // marchează "în vizitare"
    if (dist[nxti][nxtj] == -1)
        calc(nxti, nxtj);

    if (dist[nxti][nxtj] >= 0)
        dist[i][j] = dist[nxti][nxtj] + 1;
}

int main()
{
    fin >> n >> m;
    fin >> x >> y >> modx >> mody >> offsetX >> offsetY;

    if (x >= modx || y >= mody)
    {
        fout << 1 << " " << 1 << "\n";
        return 0;
    }

    for (int i = 0; i < n; ++i)
    {
        int nxti = (i * i + offsetX) % modx;
        ++fLin[nxti];
    }
    for (int j = 0; j < n; ++j)
    {
        int nxtj = (j * j + offsetY) % mody;
        ++fCol[nxtj];
    }

    reset();
    dist[x][y] = 0;
    for (int i = 0; i < modx; ++i)
        for (int j = 0; j < mody; ++j)
            calc(i, j);

    int nxti = (x * x + offsetX) % modx;
    int nxtj = (y * y + offsetY) % mody;
    int cycle = 1 + dist[nxti][nxtj];

    rasp[m / cycle + 1]++;

    for (int i = 0; i < modx; ++i)
        for (int j = 0; j < mody; ++j)
            if (dist[i][j] >= 0)
            {
                if (i == nxti && j == nxtj)
                    rasp[(m - dist[i][j] - 1) / cycle + 1] += fLin[i] * fCol[j] - 1;
                else
                    rasp[(m - dist[i][j] - 1) / cycle + 1] += fLin[i] * fCol[j];
            }

    for (int i = 1; i <= 1000000; ++i)
        if (rasp[i])
            fout << i << " " << rasp[i] << '\n';

    return 0;
}