Cod sursa(job #214222)

Utilizator zombie_testertest test zombie_tester Data 13 octombrie 2008 15:07:34
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 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;
    }