Cod sursa(job #18135)

Utilizator StTwisterKerekes Felix StTwister Data 18 februarie 2007 09:57:15
Problema Reguli Scor 70
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 1.55 kb
#include <stdio.h>

#define NMAX 500001

struct Nod
{
    int inf;
    Nod* prev;
    Nod* next;
};

typedef Nod* PNod;

long long A[NMAX];
int N;
PNod first;

void sterge(PNod nod)
{
    PNod prev = nod->prev;
    PNod next = nod->next;
    if (prev)
    {
        prev->next = next;
    }
    if (next)
    {
        next->prev = prev;
    }
}

int main()
{
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);

    scanf("%d", &N);
    for (int i = 1; i<=N; ++i)
    {
        scanf("%lld", &A[i]);
    }
    for (int i = 1; i<N; ++i)
    {
        A[i] = A[i+1] - A[i];
    }
    --N;

    first = NULL;
    PNod last = NULL;
    for (int i = 1; i<=N; ++i)
    {
        PNod nou = new Nod;
        nou->inf = i;
        nou->prev = last;
        nou->next = NULL;
        if (last)
        {
            last->next = nou;
        }
        if (!first)
            first = nou;
        last = nou;
    }

    for (int i = 2; i<=N; ++i)
    {
        PNod nod = first;
        while (nod && nod->inf<=i)
        {
            PNod urm = nod->next;
            int K = nod->inf;
            int ind = i % K;
            if (ind == 0) ind = K;
            if (A[i] != A[ind])
            {
                if (nod == first)
                    first = nod->next;
                sterge(nod);
            }
            nod = urm;
        }
    }

    int len = first->inf;
    printf("%d\n", len);
    for (int i = 1; i<=len; ++i)
    {
        printf("%lld\n", A[i]);
    }
}