Cod sursa(job #1856445)

Utilizator Vlad_317Vlad Panait Vlad_317 Data 24 ianuarie 2017 21:27:02
Problema Robotei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <cstdio>

using namespace std;

int n, m, x, y, modX, modY, offsetX, offsetY;

int d[1001][1001];
int sol[667000];
int ans, l;
void findLength(int i, int j)
{
    if(d[i][j] > 0 || (i == x && j == y))
    {
        ans = d[i][j];
        return;
    }
    if(l++ > modX * modY)
    {
        d[i][j] = -1;
        return;
    }
    findLength( (i * i + offsetX) % modX, (j * j + offsetY) % modY);
    d[i][j] = ++ans;
}

int main()
{
    FILE *fin, *fout;

    fin = fopen("robotei.in", "r");
    fout = fopen("robotei.out", "w");

    fscanf(fin, "%d%d%d%d%d%d%d%d", &n, &m, &x, &y, &modX, &modY, &offsetX, &offsetY);

    if(x >= modX || y >= modY)
    {
        fprintf(fout, "1 1");
        return 0;
    }
    int i = x, j = y;
    int cycle = 1;
    i = (i * i + offsetX) % modX;
    j = (j * j + offsetY) % modY;
    while( (i != x || j != y) && cycle <= modX * modY)
    {
        i = (i * i + offsetX) % modX;
        j = (j * j + offsetY) % modY;
        cycle++;
    }

    for(int i = 0; i < modX; i++)
        for(int j = 0; j < modY; j++)
        {
            int cate = 0;
            ans = l = 0;
            findLength(i, j);
            cate += (n - 1 - i) % modX + (n - 1 - j) % modY;
            if(d[i][j] > 0)
            {
                sol[d[i][j]] += cate * (m - d[i][j]) / cycle;
                sol[d[i][j]] += cate * (m - 1 - d[i][j]) / cycle;
            }
        }
    sol[cycle]--;
    for(int i = 1; i <= m; i++)
    {
        if(sol[i] > 0)
            fprintf(fout, "%d %d\n", i, sol[i]);
    }

    return 0;
}