Cod sursa(job #2458285)

Utilizator Iulia25Hosu Iulia Iulia25 Data 20 septembrie 2019 09:07:01
Problema Reguli Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>

using namespace std;

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

int n, k;
long long b[500005], a[500005];
int phi[500005];

int main()  {
  fin >> n;
  k = n - 1;
  fin >> b[0];
  for (int i = 1; i < n; ++i)  {
    fin >> b[i];
    a[i] = b[i] - b[i - 1];
  }
  for (int i = 2; i < n; ++i)  {
    int x = i - 1;
    while (a[phi[x] + 1] != a[i] && phi[x])  {
      x = phi[x];
    }
    if (a[phi[x] + 1] == a[i])
      phi[i] = phi[x] + 1;
    else phi[i] = 0;
    if (phi[i] == 1)
      k = i - 1;
  }
  for (int i = 1; i < n; ++i)
    if (a[i] != a[i + k])
      k = n - 1;
  fout << k << '\n';
  for (int i = 1; i <= k; ++i)
    fout << a[i] << '\n';
  return 0;
}