Cod sursa(job #18682)

Utilizator victorsbVictor Rusu victorsb Data 18 februarie 2007 12:58:08
Problema Reguli Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 0.84 kb
#include <cstdio>

#define Nmax 500005

int n;
long long nr[Nmax], sir[Nmax];
int pref[Nmax];

void citire()
{
    int i;
    scanf("%d\n", &n);
    for (i = 1; i <= n; ++i)
        scanf("%lld\n", &nr[i]);
}

void calcpref()
{
    int k = 0, q, i;
    pref[1] = 0;
    for (q = 2; q <= n; q++)
    {
        while (k > 0 && sir[k + 1] != sir[q])
            k = pref[k];
        if (sir[k + 1] == sir[q])
            k++;
        pref[q] = k;
    }
}

void solve()
{
    int i;
    --n;
    for (i = 1; i <= n; ++i)
        sir[i] = nr[i + 1] - nr[i];
    calcpref();
    printf("%d\n", n - pref[n]);
    for (i = 1; i <= n - pref[n]; ++i)
        printf("%lld\n", sir[i]);
}

int main()
{
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);
    citire();
    solve();
    return 0;
}