Cod sursa(job #215296)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 18 octombrie 2008 12:57:38
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
# include <cstdio>

# define FIN "reguli.in"
# define FOUT "reguli.out"
# define MAXN 500005

long long N,i,x,y,k,L;
long long A[MAXN];
long long P[MAXN];

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%lld %lld",&N,&x);
        for (i = 1; i < N; ++i)
          {
             scanf("%lld",&y);
             A[i] = y - x;
             x = y;
          }
          
        P[1] = 0;
        k = 0;
        for (i = 2; i < N; ++i)
          {
             while (k && A[k+1] != A[i])
               k = P[k];
             if (A[k+1] == A[i]) k++;
             P[i] = k;
          }
          
        L = N-1;
        for (i = 2; i < N && L == N-1; ++i)
          if (P[i] && i%(i-P[i])==0 && P[i]==P[N-1]-N+1+i)
            L = i - P[i];
        
        printf("%lld\n",L);
        for (i = 1; i <= L; ++i)
          printf("%lld\n",A[i]);
                        
        return 0;
    }