Cod sursa(job #1495719)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 3 octombrie 2015 15:20:16
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<stdio.h>
#include<string.h>
#define N 500000
long long dif[N+1];
int pi[N+1];
int main()
{
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    int n;
    scanf("%d",&n);
    long long a,b;
    scanf("%lld",&a);
    int i;
    for(i=1;i<=n-1;i++){
        scanf("%lld",&b);
        dif[i]=b-a;
        a=b;
    }
    int k=0;
    for(i=2;i<n;i++){
        while(k!=0&&dif[i]!=dif[k+1])
            k=pi[k];
        if(dif[i]==dif[k+1])
            k++;
        pi[i]=k;
    }
    int length=n-1-pi[n-1];
    printf("%d\n",length);
    for(i=1;i<=length;i++)
        printf("%d\n",dif[i]);
    return 0;
}