Cod sursa(job #1961902)

Utilizator BugirosRobert Bugiros Data 11 aprilie 2017 14:14:57
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <cstdio>
using namespace std;

const int MAXN = 500005;

long long v[MAXN];
int n;

int prefix[MAXN];

void citire()
{
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    scanf("%d",&n);
    for (int i = 1;i <= n;++i)
    {
        scanf("%lld",&v[i]);
        v[i - 1] = v[i] - v[i - 1];
    }

    --n;
}



void creare_prefix()
{
    int k = 0;
    prefix[1] = 0;
    for (int i = 2;i <= n;++i)
    {
        while(k > 0 && v[k + 1] != v[i])
            k = prefix[k];
        if (v[k + 1] == v[i])
        {
            ++k;
            prefix[i] = k;
        }
    }
}

int l;

int main()
{
    citire();
    creare_prefix();
    l = n - prefix[n];
    printf("%d\n",l);
    for (int i = 1;i <= l;++i)
        printf("%d\n",v[i]);
    return 0;
}