Cod sursa(job #1561805)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 4 ianuarie 2016 16:05:58
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int MAX_N = 500000;

long long V[1 + MAX_N];
int PI[1 + MAX_N];

int main() {
    int n, i, q;

    in >> n;
    for(i = 1; i <= n; i++) {
        in >> V[i];
    }
    for(i = 2; i <= n; i++) {
        V[i - 1] = V[i] - V[i - 1];
    }
    n--;

    for(i = 2, q = 0; i <= n; i++) {
        while(q > 0 && V[q + 1] != V[i]) q = PI[q];
        if(V[q + 1] == V[i]) q++;
        PI[i] = q;
    }

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

    return 0;
}