Cod sursa(job #1938079)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 24 martie 2017 16:43:19
Problema Robotei Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("robotei.in");
ofstream g("robotei.out");
int N, M, X, Y, shiftX, shiftY, modX, modY;
int A[1005][1005];
bool Use[1005][1005];
int Ans[1000005];
int ans;
void Read()
{
    f >> N >> M >> X >> Y >> modX >> modY >> shiftX >> shiftY;
    memset(A, -1, sizeof(A));
}

int precalcA(int x, int y)
{
    if(A[x][y] != -1)
        return A[x][y];
    A[x][y] = 1000000;
    if(x == X && y == Y)
    {
        A[x][y] = 0;
        return 0;
    }
    int newX = (x * x + shiftX) % modX;
    int newY = (y * y + shiftY) % modY;
    int ans = precalcA(newX, newY);
    A[x][y] = ans + 1;
    return ans + 1;
}

int CycleXY(int x, int y, int moves)
{
    Use[x][y] = 1;
    if(x == X && y == Y)
        return moves;
    int newX = (x * x + shiftX) % modX;
    int newY = (y * y + shiftY) % modY;
    if(Use[newX][newY] == 1)
        return 1000000;
    return CycleXY(newX, newY, moves + 1);
}

void Solve()
{
    --N;
    if(X > N || Y > N)
    {
        g << "0 " << N * N << "\n";
        return;
    }
    if(X >= modX || Y >= modY)
    {
        Ans[1] = 1;
        Ans[0] = N * N - 1;
        for(int i = 0; i <= M; i++)
        if(Ans[i] != 0)
        {
            g << i << " " << Ans[i] << "\n";
        }
        return;
    }
    int newX = (X * X + shiftX) % modX;
    int newY = (Y * Y + shiftY) % modY;
    int cycle = CycleXY(newX, newY, 1);
    int remx = N % modX;
    int remy = N % modY;
    for(int i = 0; i < modX; i++)
        for(int j = 0; j < modY; j++)
        {
            if(A[i][j] == -1)
                precalcA(i, j);
            int dist = A[i][j];
            int add1 = 0;
            if(M - dist >= 0)
                add1 = 1;
            int add = max(0, (M - dist) / cycle) + add1;
            int nbX = N / modX;
            int nbY = N / modY;
            if(remx >= i)
                ++nbX;
            if(remy >= j)
                ++nbY;
            if(i == X && j == Y)
            {
                Ans[add]++;
                Ans[max(0, add - 1)] += nbX * nbY - 1;
            }
            else
            Ans[add] += nbX * nbY;
        }
    for(int i = 0; i <= M; i++)
        if(Ans[i] != 0)
        {
            g << i << " " << Ans[i] << "\n";
        }
}
int main()
{
    Read();
    Solve();
    return 0;
}