Cod sursa(job #1402525)

Utilizator retrogradLucian Bicsi retrograd Data 26 martie 2015 17:10:24
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<fstream>

using namespace std;
typedef int64_t var;

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

#define MAXN 500002

var V[MAXN];
int PI[MAXN];
int n;

void build_pi() {
    PI[0] = -1;
    for(int i=1; i<=n; i++) {
        int j=PI[i-1];
        while(j != -1 && V[i] != V[j+1])
            j = PI[j];
        PI[i] = j+1;
    }
}

int main() {

    fin>>n;
    for(int i=1; i<=n; i++) {
        fin>>V[i];
    }
    for(int i=n; i>=1; i--) {
        V[i] -= V[i-1];
    }
    for(int i=1; i<n; i++) {
        V[i] = V[i+1];
    }
    n--;
    build_pi();

    fout<<n-PI[n]<<'\n';

    for(int i=1; i<=n-PI[n]; i++) {
        fout<<V[i]<<'\n';
    }

    return 0;
}