Cod sursa(job #1913665)

Utilizator delta_wolfAndrei Stoica delta_wolf Data 8 martie 2017 13:33:06
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>
using namespace std;
long long n, v[500001], pi[500001], k, sol;

int main()
{
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);

    long long i;

    scanf("%lld", &n);
    for(i = 0; i < n; ++i)
    {
        scanf("%lld", &v[i]);
    }
    for(i = n - 1; i > 0; --i)
    {
        v[i] -= v[i - 1];
    }


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

    sol = n - 1 - pi[n - 1];

    printf("%lld\n",sol);

    for(i = 1; i <= sol; ++i)
    {
        printf("%lld\n", v[i]);
    }


    return 0;
}