Cod sursa(job #572302)

Utilizator bogfodorBogdan Fodor bogfodor Data 5 aprilie 2011 10:44:03
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <cstdio>
#define Nmax 500007
using namespace std;

FILE *fin=freopen("reguli.in","r",stdin);
FILE *fout=freopen("reguli.out","w",stdout);

long long a[Nmax],dif[Nmax],p[Nmax];
int k;

void citire();
void prefix();
void afisare();

int main()
{
    citire();
    prefix();
    afisare();
    return 0;
}

void citire()
{
    scanf("%d %lld",&k,&a[0]);
    for(int i=1;i<k;i++){
        scanf("%lld",&a[i]);
        dif[i]=a[i]-a[i-1];
    }
}

void prefix()
{
    int x=0;
    for(int i=2;i<k;i++)
    {
        while(x >0 && dif[x+1]!=dif[i])
            x=p[x];
        if(dif[x+1]==dif[i])
            x++;
        p[i]=x;
    }
}

void afisare()
{
    int r=k-p[k-1]-1;
    printf("%d\n",r);
    for(int i=1;i<=r;i++)
        printf("%lld\n",dif[i]);
}