Cod sursa(job #1880868)

Utilizator sfechisalin@yahoo.comSfechis Alin [email protected] Data 15 februarie 2017 22:52:25
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>
#define NN 500005
using namespace std;
ifstream fin("reguli.in");
ofstream fout("reguli.out");

int n;
long long a[NN],x,y;
int main()
{
    fin >> n;
    fin >> x;
    for (int i = 2;i <= n; ++i)
    {
        fin >> y;
        a[++a[0]] = y - x;
        x = y;
    }

    vector<int>pi(a[0] + 1,0);
    int k = 0;
    for(int i = 2;i <= a[0];++i)
    {
        while (k && a[k+1] != a[i])
            k = pi[k];
        if (a[k+1] == a[i])
            k++;
        pi[i] = k;
    }

    int D = 0,p_start;
    for (int i = a[0]; i>=0 && !D; --i)
    {
      p_start = i - pi[i];
      if (pi[i] % p_start == 0 && pi[i])
        D = p_start;
    }

    fout << a[0] - pi[a[0]] << "\n";
    for (int i = 1; i <= a[0] - pi[a[0]];++i)
        fout << a[i] << "\n";

    return 0;
}