Cod sursa(job #19212)

Utilizator georgianaGane Andreea georgiana Data 18 februarie 2007 22:08:22
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <stdio.h>

long long int x[500001];
int n,k,prefix[500001];

int main()
{
   freopen("reguli.in","r",stdin);
   scanf("%d",&n);
   for (int i=0;i<n;i++) scanf("%lld",&x[i]);
   for (int i=n-1;i>0;i--) x[i]-=x[i-1];

   prefix[1]=0;
   for (int i=2;i<n;i++)
      {
         k=prefix[i-1];
         while (x[k+1]!=x[i] && k>0) k=prefix[k];
         if (x[k+1]==x[i]) prefix[i]=k+1;
         else prefix[i]=0;
      }
   k=n-1-prefix[n-1];

   freopen("reguli.out","w",stdout);
   printf("%d\n",k);
   for (int i=1;i<=k;i++)
      printf("%lld\n",x[i]);
   fclose(stdout);
   return 0;
}