Cod sursa(job #966661)

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

#define maxn 500001

int N ;
int 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("%d", &N);

    int x1, x2;
    scanf("%d", &x1);

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

    prefix() ;

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

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

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

    return 0;
}