Cod sursa(job #17057)

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

#include <stdio.h>
#include <string.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 extract(void)
{
    int i, l;
    ll x = 0;
    char s[32];

    fgets(s, sizeof(s), stdin);
    l = strlen(s);
    for (i = (s[0]=='-'); i < l; i++)
        if (s[i] >= '0' && s[i] <= '9')
           x = x * 10 + (s[i] - '0');
        else
            break;
    if (s[0] == '-') x = -x;
            
    return x;
}

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", &N);
        
    ant = extract();
    for (i = 2; i <= N; i++)
    {
        x = extract();
        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("%lld\n", v[i]);
    
    return 0;
}