Cod sursa(job #931072)

Utilizator PatrikStepan Patrik Patrik Data 27 martie 2013 22:58:39
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
    #include<cstdio>
    using namespace std;
    #define MAX 500001
    int N , maxx , poz , q , pi[MAX] , rez;
    long long x[MAX] , a[MAX] ;

    void citire();
    void solve();
    void tipar();

    int main()
    {
        citire();
        solve();
        tipar();
        return 0;
    }

    void citire()
    {
        freopen("reguli.in" , "r" , stdin );
        scanf("%d" , &N);
        for(int i = 0 ; i < N ; ++i )
            scanf("%lld" , &x[i]);
    }

    void solve()
    {
        for(int i = 1 ; i <N ; ++i )
            a[i]=x[i]-x[i-1];
        q = 0;
        for(int i = 2 ; i < N ; ++i )
        {
            while(a[i]!=a[q+1] && q)
                q = pi[q];
            if(a[i]==a[q+1])
                ++q;
            pi[i] = q;
            if(pi[i] > maxx)
            {
                maxx = pi[i];
                poz = i;
            }
        }
        if(poz == N-1)rez = N-1;
        else rez = poz-pi[poz];
    }

    void tipar()
    {
        freopen("reguli.out" , "w" , stdout );
        printf("%d\n" , rez);
        for(int i = 1 ; i <= rez ; ++i )
            printf("%lld\n" , a[i]);
    }