Cod sursa(job #17044)

Utilizator filipbFilip Cristian Buruiana filipb Data 14 februarie 2007 19:49:20
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
// O(N) time and memory

#include <stdio.h>
#include <assert.h>
#define ll long long
#define NMax 500005

int N;
ll v[NMax]; int pi[NMax], ok[NMax];

void functie_prefix(void)
{
     int i, k;
     
     pi[1] = 0; k = 0;
     for (i = 2; i <= N; i++)
     {
         while (k > 0 && v[k+1] != v[i])
               k = pi[k];
         if (v[k+1] == v[i])
            k++;
            
         pi[i] = k;
     }
     
}

int main(void)
{
    int i, K, c, r, sol = 0;
    ll x, ant;
    
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);
    
    scanf("%d", &N);
    
    assert(5 <= N && N <= 500000);
    
    scanf("%I64d", &ant);
    for (i = 2; i <= N; i++)
    {
        scanf("%I64d", &x);
        v[i-1] = x-ant;
        ant = x;
    }
    N--;
    
    functie_prefix();
    for (r = N; r; r = pi[r])
        ok[pi[r]] = 1;
    
    for (K = 1; K <= N; K++)
    {
        c = N / K; r = N % K;
        
        if (pi[N-r] > 0 && (N-r) % (N-r-pi[N-r]) == 0 && 
            (N-r) / (N-r-pi[N-r]) == c && ok[r])
            { sol = 1; break; }
    }
    
    if (!sol) K--;
    
    printf("%d\n", K);
    for (i = 1; i <= K; i++)
        printf("%I64d\n", v[i]);
    
    return 0;
}