Cod sursa(job #1305762)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 30 decembrie 2014 03:49:41
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
using namespace std;

const int MAX_N = 500002;

int N;
int Pi[MAX_N];
long long a[MAX_N], v[MAX_N];

int main() {
    ifstream f("reguli.in");
    ofstream g("reguli.out");

    f >> N;
    for(int i = 0; i < N; ++i) {
        f >> a[i];

        if(i > 0)
            v[i] = a[i] - a[i - 1];
    }

    for(int i = 2; i < N; ++i) {
        int p = Pi[i - 1];

        while(p && v[p + 1] != v[i])
            p = Pi[p];
        if(v[p + 1] == v[i])
            ++p;
        Pi[i] = p;
    }

    --N;

    int ans = N - Pi[N];

    g << ans << "\n";
    for(int i = 1; i <= ans; ++i)
        g << v[i] << "\n";

    f.close();
    g.close();

    return 0;
}