Cod sursa(job #2603695)

Utilizator lucametehauDart Monkey lucametehau Data 20 aprilie 2020 17:56:08
Problema Robotei Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 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[45000];
int dp[1005][1005];
bool viz[1005][1005];
int cntx[1005], cnty[1005], ctx[1005], cty[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)]++;
    if(i < modx)
      ctx[trans(i, offx, modx)]++;
  }
  for(int i = 0; i < n; i++) {
    cnty[trans(i, offy, mody)]++;
    if(i < mody)
      cty[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 per = dp[trans(X, offx, modx)][trans(Y, offy, mody)] + 1;
  for(int i = 0; i < modx; i++) {
    for(int j = 0; j < mody; j++) {
      if(dp[i][j] < 0) {
        ans[0] += cntx[i] * cnty[j] - (i == trans(X, offx, modx) && j == trans(Y, offy, mody));
        continue;
      }
      if(dp[i][j] > m)
        ans[0]++;
      else
        ans[1 + (m - dp[i][j]) / per]++;
      if(dp[i][j] + 1 > m)
        ans[0] += cntx[i] * cnty[j] - ctx[i] * cty[j];
      else
        ans[1 + (m - dp[i][j] - 1) / per] += cntx[i] * cnty[j] - ctx[i] * cty[j];
    }
  }
  for(int i = 0; i <= m; i++) {
    if(ans[i])
      cout << i << " " << ans[i] << "\n";
  }
  return 0;
}