Cod sursa(job #1554134)

Utilizator andru47Stefanescu Andru andru47 Data 20 decembrie 2015 22:48:07
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 500000 + 5;
long long n,x,y,phi[NMAX],a[NMAX];
int main()
{
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    scanf("%lld\n", &n);
    scanf("%lld\n", &x);
    for (int i = 2; i<=n; ++i)
    {
        scanf("%lld", &y);
        a[i-1]=y-x;
        x=y;
    }
    phi[1]=0;
    --n;
    int k;
    for (int i = 2; i<=n; ++i)
    {
        k=phi[i-1];
        while(a[k+1]!=a[i]&&k>0)
            k=phi[k];
        if (a[i]==a[k+1])phi[i]=k+1;
        else phi[i]=0;
    }
    printf("%lld\n", n-phi[n]);
    for (int i = 1; i<=n-phi[n]; ++++--i)
        printf("%lld\n", a[i]);
    return 0;
}