Cod sursa(job #861934)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 22 ianuarie 2013 00:22:38
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb

#include <cstdio>
#include <fstream>

using namespace std;

typedef long long I64;

const int N = 500005;

I64 A[N],x,last;
int n,P[N];

void READ ()
{
    ifstream in ("reguli.in");
    in>>n;
    for(int i=1;i<=n;++i)
    {
        in>>x;
        A[i-1] = x - last ;
        last = x ;
    }
    --n;
    A[0]=0;
}

void SOLVE ()
{
    int q=0;
    for(int i=2;i<=n;++i)
    {
        for(;q&&A[i]!=A[q+1];q=P[q]);
        if(A[i]==A[q+1])
            ++q;
        P[i]=q;
    }
    n-=P[n];
}

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

int main ()
{
    READ ();
    SOLVE ();
    OUT ();
    return 0;
}