Cod sursa(job #1856455)

Utilizator Vlad_317Vlad Panait Vlad_317 Data 24 ianuarie 2017 21:43:30
Problema Robotei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 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)
    {
        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++;
    }

    if(cycle > modX * modY)
    {
        int nr = 0;
        for(int i = 0; i < modX; i++)
            for(int j = 0; j < modY; j++)
            {
                ans = l = 0;
                findLength(i, j);
                if(l < modX * modY)
                    nr++;
            }
        fprintf(fout, "1 %d\n", nr);

    }
    else
    {

        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 = 0; i <= m; i++)
    {
        if(sol[i] > 0)
            fprintf(fout, "%d %d\n", i, sol[i]);
    }

    return 0;
}