Cod sursa(job #17999)

Utilizator filipbFilip Cristian Buruiana filipb Data 17 februarie 2007 20:33:16
Problema Reguli Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
// O(N) time and memory

#include <stdio.h>
#include <assert.h>
#define min(a, b) ((a < b) ? a : b)
#define ll long long
#define NMax 500005

int N;
ll v[NMax]; int pi[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;
    ll x, ant;
    
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);
    
    scanf("%d", &N);
    
    assert(5 <= N && N <= 500000);
    
    scanf("%lld", &ant);
    for (i = 2; i <= N; i++)
    {
        scanf("%lld", &x);
        v[i-1] = x-ant;
        ant = x;
    }
    N--;
    
    functie_prefix();
    
    K = N;
    for (r = pi[N]; r; r = pi[r])
        if (pi[N-r] > 0 && (N-r) % (N-r-pi[N-r]) == 0 &&
            (N-r) / (N-r-pi[N-r]) > r)
                  K = min(K, N-r-pi[N-r]);
    
    printf("%d\n", K);
    for (i = 1; i <= K; i++)
        printf("%lld\n", v[i]);

    return 0;
}