Cod sursa(job #40405)

Utilizator andrei_infoMirestean Andrei andrei_info Data 27 martie 2007 13:42:31
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <stdio.h>
#include <string.h>
#define nmax 500005
long n, p[nmax];
long long int s[nmax];

void read();
void prefix();
void prefixmare();

int main()
{
memset(p,0,sizeof(p));
memset(s,0,sizeof(s));
read();
prefix();
prefixmare();
return 0;
}

void read()
{
long i;
long long int x,x1;
freopen("regulic.in","r",stdin);
scanf("%ld", &n);
scanf("%lld", &x);
for (i=1; i<n; i++)
    {
    scanf("%lld", &x1);
    s[i] = x1-x;
    x=x1;
    }
n-=1;
fclose(stdin);
}

void prefix()
{
long q,k;
p[1]=0; k=0;
for (q=2; q<=n; q++)
    {
    while ( k>0 && s[k+1] != s[q])
          k=p[k];
    if (s[k+1] == s[q]) k+=1;
    p[q]=k;
    }
}

void prefixmare()
{
long i,ok;
long long int lmin, max=0;
for (i=2; i<=n; i++)
    if ( (p[i] >0) && ( i % (i-p[i])==0 ) )
       max=i;
if (max == 0)
   {
   max = n;
   lmin = n;
   }
else lmin=max-p[max];
if ((max < n ) && (n-max >= lmin) )
   {
   lmin = n;
   max = n;
   }
if ((max < n) && ( n-max < lmin))
   {
   ok=1;
   for (i = max+1; i<=n; i++)
       if (s[i] != s[i-max])
          {
          ok=0;
          break;
          }
   if (ok==0)
          {
          max=n;
          lmin=n;
          }
   }

freopen("reguli.out","w",stdout);
printf("%lld\n",lmin);
for (i=1; i<=lmin; i++)
    printf("%lld\n",s[i]);
fclose(stdout);
}