Cod sursa(job #19020)

Utilizator alextheroTandrau Alexandru alexthero Data 18 februarie 2007 17:46:04
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <cstdio>

#define nmax 500005

int x[nmax],pi[nmax];
long long a[nmax];
int n;

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

int main() {
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);

    scanf("%d",&n);
    
    for(int i = 0; i < n; i++) scanf("%lld",&a[i]);
    for(int i = 1; i < n; i++) x[i] = a[i] - a[i - 1];
    
    prefix();
    int last = n - 1 - pi[n - 1];
    printf("%d\n",last);
    for(int i = 1; i <= last; i++) printf("%lld\n",x[i]);

    return 0;
}