Cod sursa(job #1405024)

Utilizator Athena99Anghel Anca Athena99 Data 28 martie 2015 19:27:55
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>

using namespace std;

ifstream fin("reguli.in");
ofstream fout("reguli.out");

const int nmax= 500000;

int n;
int dif[nmax+1], pi[nmax+1];

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

        pi[i]= k;
    }
}

int main(  ) {
    fin>>n;
    for ( int i= 1, x, last= 0; i<=n; ++i ) {
        fin>>x;

        dif[i-1]= x-last;
        last= x;
    }
    --n, dif[0]= 0;
    prefix();

    int per= 0;
    for ( int i= n; i>=1 && per==0; --i ) {
        if ( i%(i-pi[i])==0 && pi[n]>=n-i ) {
            per= i-pi[i];
        }
    }

    if ( per==0 ) per= n;
    fout<<per<<"\n";
    for ( int i= 1; i<=per; ++i ) {
        fout<<dif[i]<<"\n";
    }

    return 0;
}