Cod sursa(job #785758)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 9 septembrie 2012 20:10:27
Problema Reguli Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <cstdio>

using namespace std;

typedef long long LL;

const int MaxN = 500005;

int N, K, Pi[MaxN];
LL X[MaxN];

void Solve() {
    for (int i = N; i; --i)
        X[i] -= X[i-1];
    Pi[1] = 1;
    for (int i = 2, p = 0; i <= N; ++i) {
        for (; p && X[i] != X[p+1]; p = Pi[p]);
        p += (X[i] == X[p+1]);
        Pi[i] = p;
    }
    K = N-Pi[N];
}

void Read() {
    freopen("reguli.in", "r", stdin);
    scanf("%d", &N); --N;
    for (int i = 0; i <= N; ++i)
        scanf("%lld", &X[i]);
}

void Print() {
    freopen("reguli.out", "w", stdout);
    printf("%d\n", K);
    for (int i = 1; i <= K; ++i)
        printf("%lld\n", X[i]);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}