Cod sursa(job #148205)

Utilizator DorinOltean Dorin Dorin Data 3 martie 2008 23:14:25
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
# include <stdio.h>

# define input "reguli.in"
# define output "reguli.out"

# define max 500001

int i,x,y,j,n,q,r,c,l;
int a[max],ant[max];
bool u[max];


int main()
{
    freopen( input, "r", stdin ); 
    freopen( output, "w", stdout );
    
    scanf("%d",&n);
    scanf("%d",&x);
    
    for(i = 1 ;i < n;i ++)
    {
          scanf("%d",&y);
          a[i] = y-x;
          x = y;
    }
    
    q = 0;

    for(i = 2;i<n;i++)
    {
          while(a[q+1]!=a[i] && q)
             q = ant[q];
          if(a[q+1] == a[i])
             q++;
          ant[i] = q;
//          printf("%d ",ant[i]);
    }
    
//    printf("\n");
    
    for(i = ant[n-1];i;i=ant[i])  {   u[i] = true;}
    
    u[0] = 1;
    n--;
    for(l=1;l<n;l++)
    {
      
       c = n/l;
       r = n%l;
       if(!u[r])
          continue;

       if(!ant[n-r])
          if(n-r > l)
         continue;
       if((n-r)%(n-r-ant[n-r]))
         continue;
       if((n-r) / (n-r-ant[n-r]) != c)
         continue;
         
       break;
    }
    
    printf("%d\n",l);
    for(i=1;i<=l;i++)
       printf("%d\n",a[i]);
    
    return 0;
}