Cod sursa(job #1495272)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 2 octombrie 2015 20:39:35
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<fstream>

using namespace std;

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

const int nmax = 500000;
long long v[ nmax + 1 ];
int pi[ nmax + 1 ];

int main() {
    int n;
    long long x, y;
    fin >> n >> y;
    for( int i = 1; i < n; ++ i ) {
        fin >> x;
        v[ i ] = x - y;
        y = x;
    }

    pi[ 1 ] = 0;
    for( int i = 2; i < n; ++ i ) {
        int r = pi[ i - 1 ];
        while ( r != 0 && v[ r + 1 ] != v[ i ] ) {
            r = pi[ r ];
        }
        if ( v[ r + 1 ] == v[ i ] ) {
            pi[ i ] = r + 1;
        } else {
            pi[ i ] = 0;
        }
    }
    fout << n - 1 - pi[ n - 1 ] << "\n";
    for( int i = 1; i <= n - 1 - pi[ n - 1 ]; ++ i ) {
        fout << v[ i ] << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}