Cod sursa(job #1417669)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 10 aprilie 2015 19:33:44
Problema Reguli Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <stdio.h>
#define MAXN 500000
int pi[MAXN];
long long v[MAXN];
int main(){
    int n, i, r;
    long long x, y;
    FILE *fin, *fout;
    fin=fopen("reguli.in", "r");
    fout=fopen("reguli.out", "w");
    fscanf(fin, "%d%lld", &n, &x);
    for(i=1; i<n; i++){
        fscanf(fin, "%lld", &y);
        v[i]=y-x;
        x=y;
    }
    r=pi[0]=0;
    for(i=2; i<n; i++){
        while((r!=0)&&(v[r+1]!=v[i])){
            r=pi[r];
        }
        if(v[r+1]==v[i]){
            r++;
        }
        pi[i]=r;
    }
    fprintf(fout, "%d\n", n-1-pi[n-1]);
    for(i=1; i<n-pi[n-1]; i++){
        fprintf(fout, "%lld\n", v[i]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}