Cod sursa(job #2193711)

Utilizator lucametehauDart Monkey lucametehau Data 11 aprilie 2018 09:02:35
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>

using namespace std;

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

const int nmax = 500000;

int n;
int k;
long long x, y;

long long pat[1 + nmax];
int lps[1 + nmax];

int main() {
  cin >> n >> x;
  for(int i = 2; i <= n; i++) {
    cin >> y;
    pat[i - 1] = y - x;
    x = y;
  }
  // calculam lps-ul
  int i = 0, j = 2;
  n--;
  lps[1] = 0;
  while(j <= n) {
    if(pat[i + 1] == pat[j]) {
      i++;
      lps[j] = i;
      j++;
    } else {
      if(i)
        i = lps[i];
      else {
        lps[j] = 0;
        j++;
      }
    }
  }
  k = n - lps[n];
  cout << k << "\n";
  for(int i = 1; i <= k; i++)
    cout << pat[i] << "\n";
  return 0;
}