Cod sursa(job #23271)

Utilizator StTwisterKerekes Felix StTwister Data 28 februarie 2007 16:00:20
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>

#define NMAX 500001

int N;
int A[NMAX];
int pi[NMAX];

void prefix()
{
    int q = 0;
    pi[1] = 0;
    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;
    }
}

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

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

    --N;

    for (int i = 1; i<=N; ++i)
    {
        A[i] = A[i+1]-A[i];
    }

    prefix();

    int min = N;
    for (int L = 1; L<=N; ++L)
    {
        int c = N/L;
        int r = N%L;
        int d1 = N-r;
        int d2 = pi[N-r];

        if (d2>0 && d1 % (d1-d2) == 0 && (d1) / (d1-d2) == c)
        {
            min = L;
            break;
        }
    }

    printf("%d\n", min);
    for (int i = 1; i<=min; printf("%d\n", A[i]), ++i);
}