Cod sursa(job #1382671)

Utilizator TibixbAndrei Tiberiu Tibixb Data 9 martie 2015 13:33:38
Problema Reguli Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<fstream>
using namespace std;
long long n, i, j, x, y, a[500003], L, p[500003], ok;
ifstream in("reguli.in");
ofstream out("reguli.out");
int main(){
    in>>n;
    in>>y;
    for(i=2; i<=n; i++){
        x=y;
        in>>y;
        a[i-1]=y-x;
    }
    for(i=2; i<n; i++){
        while(L!=0 && a[i]!=a[L+1])
            L=p[L];
        if(a[i]==a[L+1])
            L++;
        p[i]=L;
    }
    for(i=n-1; i>=1; i--)
        if(p[i]>0 && i%(i-p[i])==0){
            x=i;
            //out<<i-p[i]<<"\n";
            //for(j=1; j<=i-p[i]; j++)
                //out<<a[j]<<"\n";
            break;
        }
    for(j=i+1, i=1; j<n; j++){
        if(a[i]!=a[j]){
            y=j;
            ok=1;
        }
    }
    if(ok){
        out<<y<<"\n";
        for(j=1; j<=y; j++)
            out<<a[j]<<"\n";
    }
    else{
        out<<x-p[x]<<"\n";
            for(j=1; j<=x-p[x]; j++)
                out<<a[j]<<"\n";
    }
return 0;
}