Cod sursa(job #2603721)

Utilizator lucametehauDart Monkey lucametehau Data 20 aprilie 2020 18:31:39
Problema Robotei Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>

using namespace std;

ifstream cin ("robotei.in");
ofstream cout ("robotei.out");

int n, m, X, Y, offx, offy, modx, mody;

int ans[1000000];
int dp[1005][1005];
bool viz[1005][1005];
int cntx[1005], cnty[1005];

int trans(int x, int off, int mod) {
  return (x * x + off) % mod;
}

int calc(int x, int y) {
  if(dp[x][y] != -1)
    return dp[x][y];
  if(viz[x][y])
    return (int)1e9;
  viz[x][y] = 1;
  dp[x][y] = 1 + calc(trans(x, offx, modx), trans(y, offy, mody));
  return dp[x][y];
}

int main() {
  cin >> n >> m >> X >> Y >> modx >> mody >> offx >> offy;
  for(int i = 0; i < n; i++)
    cntx[trans(i, offx, modx)]++;
  for(int i = 0; i < n; i++)
    cnty[trans(i, offy, mody)]++;
  for(int i = 0; i < modx; i++) {
    for(int j = 0; j < mody; j++)
      dp[i][j] = -1;
  }
  dp[X][Y] = 0;
  viz[X][Y] = 1;
  for(int i = 0; i < modx; i++) {
    for(int j = 0; j < mody; j++)
      dp[i][j] = calc(i, j);
  }
  int x2 = trans(X, offx, modx), y2 = trans(Y, offy, mody), per = dp[x2][y2] + 1;
  for(int i = 0; i < modx; i++) {
    for(int j = 0; j < mody; j++) {
      int nr = cntx[i] * cnty[j];
      if(i == x2 && j == y2) {
        nr--;
        if(dp[i][j] + 1 > m)
          ans[1]++;
        else
          ans[2 + (m - dp[i][j] - 1) / per]++;
      }
      if(dp[i][j] + 1 > m)
        ans[0] += nr;
      else
        ans[1 + (m - dp[i][j] - 1) / per] += nr;
    }
  }
  for(int i = 0; i <= m; i++) {
    if(ans[i])
      cout << i << " " << ans[i] << "\n";
  }
  return 0;
}