Cod sursa(job #2085702)

Utilizator GoogalAbabei Daniel Googal Data 10 decembrie 2017 16:29:07
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 500000;

int n;
long long v[1 + NMAX];
long long d[1 + NMAX];
long long pref[1 + NMAX];

int main()
{
  in >> n;
  for(int i = 1; i <= n; i++)
    in >> v[i];
  for(int i = 2; i <= n; i++)
    d[i - 1] = v[i] - v[i - 1];

  int j = 0;
  for(int i = 2; i < n; i++) {
    while(j != 0 && d[j + 1] != d[i])
      j = pref[j];
    if(d[j + 1] == d[i])
      j++;
    pref[i] = j;
  }

  out << n - pref[n - 1] - 1 << '\n';

  for(int i = 1; i < n - pref[n - 1]; i++)
    out << d[i] << '\n';
  in.close();
  out.close();
  return 0;
}