Cod sursa(job #912564)

Utilizator FayedStratulat Alexandru Fayed Data 12 martie 2013 15:26:26
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>
#include <list>
#define NMAX 500001
using namespace std;

int Prefix[NMAX],aparitii[NMAX];
long long int n,x1,x2,nr;

int main(){

    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    scanf("%ld",&n);
    scanf("%ld",&x1);
    for(register int i=1;i<n;++i){
        scanf("%ld",&x2);
        aparitii[i] = x2-x1;
       x1 = x2;
    }

     int k=0;
        for(register int i=2;i<n;++i){
            while(k>0 && aparitii[k+1]!=aparitii[i]) k = Prefix[k];
            if(aparitii[k+1]==aparitii[i])
                k++;
             Prefix[i] = k;
        }

nr = (n-1) - Prefix[n-1];
printf("%ld\n",nr);
for(register int i=1;i<=nr;++i)
printf("%ld\n",aparitii[i]);

return 0;
}