Cod sursa(job #1241376)

Utilizator teoionescuIonescu Teodor teoionescu Data 13 octombrie 2014 13:49:36
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 kb
#include<fstream>
using namespace std;
ifstream in("reguli.in");
ofstream out("reguli.out");
const int Nmax = 500001;
int N,v[Nmax],pi[Nmax];
int main(){
    in>>N;
    for(int i=0;i<N;i++) in>>v[i]; N--;
    for(int i=N;i>=1;i--) v[i]-=v[i-1];
    for(int i=0;i<N;i++) v[i]=v[i+1];
    int w=0;
    for(int i=1;i<N;i++){
        while(w && v[i]!=v[w]) w=pi[w-1];
        if(v[i]==v[w]) w++;
        pi[i]=w;
    }
    out<<N-pi[N-1]<<'\n';
    for(int i=0;i<N-pi[N-1];i++) out<<v[i]<<'\n';
    return 0;
}