Cod sursa(job #966662)

Utilizator matei_cChristescu Matei matei_c Data 26 iunie 2013 13:37:08
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<cstdio>
using namespace std ;

#define maxn 500001

long long N ;
long long pi[maxn], sir[maxn] ;

void prefix()
{
    int k = 0 ;

    for(int poz = 2; poz < N; ++poz )
    {
        while( sir[poz] != sir[ k + 1 ] && k > 0 )
            k = pi[k] ;

        if( sir[poz] == sir[ k + 1 ] )
            ++k ;

        pi[poz] = k ;
    }
}

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

    scanf("%lld", &N);

    long long x1, x2;
    scanf("%lld", &x1);

    for(int i = 1; i < N; ++i )
    {
        scanf("%lld", &x2);
        sir[i] = x2 - x1 ;
        x1 = x2 ;
    }

    prefix() ;

    long long len = N - 1 - pi[ N - 1 ] ;

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

    for(int i = 1; i <= len; ++i )
        printf("%lld\n", sir[i]);

    return 0;
}