Cod sursa(job #148155)

Utilizator DorinOltean Dorin Dorin Data 3 martie 2008 22:37:15
Problema Reguli Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 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;
    }
    n--;
    
    for(i = ant[n];i;i=ant[i])     u[i] = true;
    
    for(l=1;l<=n;l++)
    {
       c = n/l;
       r = n%l;
       if(!u[c])
          continue;
       if(!ant[n-r])
         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;
}