Cod sursa(job #216857)

Utilizator Mishu91Andrei Misarca Mishu91 Data 25 octombrie 2008 23:24:59
Problema Reguli Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
#include <bitset>
using namespace std;

#define MAX_N 500007

int N;
long long V[MAX_N], S[MAX_N];
long long pi[MAX_N];
bitset <MAX_N>ok;

void citire()
{
    scanf("%d\n",&N);

    for(int i = 0; i < N; ++i)
        scanf("%d", V+i);
    --N;
}

void kmp()
{
    int i, q = 0;
    for(i = 2, pi[1] = 0; i <= N; ++i)
    {
        while(q && S[q+1] != S[i])
            q = pi[q];
        if(S[q+1] == S[i])
            ++q;
        pi[i] = q;
    }
    q = N;
    while(q)
    {
        q = pi[q];
        ok[q] = 1;
    }
}

void solve()
{
    for(int i = 1; i <= N; ++i)
        S[i] = V[i] - V[i-1];
    int L = (N >> 1), i;
    kmp();

    for(i = 1; i <= L; ++i)
    {
        int r = N % i;
        int c = N / i;
        int pN = N - r;

        if(pi[pN] && (pN % (pN - pi[pN]) == 0) && ((pN / (pN - pi[pN])) % c == 0) && ok[r])
            break;
    }

    if(i <= L)
    {
        printf("%d\n", i);

        for(int j = 1; j <= i; ++j)
            printf("%lld\n", S[j]);
        return;
    }

    for(i = L + 1; i < N; ++i)
    {
        int r = N % i;
        int pN = N -r;
        if(pi[pN] && ok[r])
            break;
    }
    printf("%d\n", i);

    for(int j = 1; j <= i; ++j)
        printf("%lld\n", S[j]);
}

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

    citire();
    solve();
}