Cod sursa(job #18514)

Utilizator astronomyAirinei Adrian astronomy Data 18 februarie 2007 12:30:34
Problema Ghiozdan Scor 0
Compilator c Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 1.24 kb
#include <stdio.h>

#define MAXN (1 << 19)

typedef long long llong;

int N, K, P[MAXN];
llong text[MAXN];

void solve(void)
{
    int i, k;

    for(i = N-1; i >= 1; i--)
        text[i] = text[i]-text[i-1];

    for(k = 0, i = 2; i < N; i++)
    {
        while(text[k+1] != text[i] && k > 0)
            k = P[k];
        if(text[k+1] == text[i])
            k++;
        P[i] = k;
    }

    K = N-1-P[N-1];
}

void read_data(void)
{
    int i, ind, minus;
    char sir[1024];
    llong x;
    
    scanf("%d\n", &N);

    for(i = 0; i < N; i++)
    {
        fgets(sir, 1024, stdin), ind = 0, x = 0;

        if(sir[0] == '-')
            minus = 1, ind++;
        else
            minus = 0;

        for(; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
            x = x*10+(llong)(sir[ind]-48);

        if(minus)
            text[i] = x*(-1);
        else
            text[i] = x;
    }
}

void write_data(void)
{
    int i;

    printf("%d\n", K);

    for(i = 1; i <= K; i++)
        printf("%lld\n", text[i]);
}

int main(void)
{
    freopen("reguli.in", "rt", stdin);
    freopen("reguli.out", "wt", stdout);

    read_data();
    solve();
    write_data();

    return 0;
}