Cod sursa(job #884916)

Utilizator visanrVisan Radu visanr Data 21 februarie 2013 14:26:23
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define Nmax 500010

int N, X[Nmax], A[Nmax], PI[Nmax], Q;

int main()
{
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);
    scanf("%i %i", &N, &X[1]);
    for(int i = 2; i <= N; ++i)
    {
        scanf("%i", &X[i]);
        A[i - 1] = X[i] - X[i - 1];
    }
    -- N;
    for(int i = 2; i <= N; ++i)
    {
        while(Q && A[Q + 1] != A[i]) Q = PI[Q];
        if(A[Q + 1] == A[i]) Q ++;
        PI[i] = Q;
    }
    printf("%i\n", N - PI[N]);
    for(int i = 1; i <= N - PI[N]; ++i)
        printf("%i\n", A[i]);
    return 0;
}