Cod sursa(job #392283)

Utilizator vicenzo_cnuStan Alexandru Dan vicenzo_cnu Data 7 februarie 2010 09:03:55
Problema Reguli Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>
#define Nmax 500005
long long a[Nmax],n,D[Nmax],l,pi[Nmax];
int verific(int r,int z)
{int i;
for(i=n-r+1;i<=n;i++)
if(D[i]!=D[i%z])
return 0;
return 1;}

int main()
{freopen("reguli.in","r",stdin);
freopen("reguli.out","w",stdout);
scanf("%d",&n);
long long i;
  for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
n--;
  for(i=1;i<=n;i++)
    D[i]=a[i+1]-a[i];
pi[1]=0;long long q=0,r=0,c=0,ha=1;
  for(i=2;i<=n;i++)
  {	while(q && D[q+1]!=D[i])
          q=pi[q];
        if(D[q+1]==D[i])
          q++;
        pi[i]=q;
       // printf("%d ",pi[i]);
        }
  l=n;      
    for(i=2;i<=n;i++)
    {r=n%i;
    c=n/i;
    ha=n-r-pi[n-r];
   // printf("%d %d %d %d\n",i,r,c,ha);
   if(c>1)
    {if(pi[n-r] && (n-r)%ha==0 && (n-r)/ha==c  && verific(r,i))
    {l=i;break;}}
   else if(verific(r,i))
   {l=i;break;}
}
    
  printf("%d\n",l);
  for(i=1;i<=l;i++)
  printf("%d\n",D[i]);
  fclose(stdin);
  fclose(stdout);
  return 0;
  }