Cod sursa(job #1988469)

Utilizator DjokValeriu Motroi Djok Data 3 iunie 2017 09:12:05
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <bits/stdc++.h>
using namespace std;

const int N = 500005;

int i, n, k;
long long a[N], pref[N], b[N];

int main() {
  ifstream cin("reguli.in");
  ofstream cout("reguli.out");
  ios_base::sync_with_stdio(0);

  cin >> n;
  for(i = 1; i <= n; ++i) cin >> a[i];
  for(i = 0; i + 1< n; ++i) b[i] = a[i + 2] - a[i + 1];

  for(i = 1; i < n - 1; ++i) {
    while(k && b[k] != b[i]) k = pref[k - 1];
    if(b[k] == b[i]) ++k;
    pref[i] = k;
  }

  cout << n - k - 1 << '\n';
  for(i = 0; i < n - k - 1; ++i) cout << b[i] << '\n';

  return 0;
}