Cod sursa(job #329853)

Utilizator aladinaladin aladinn aladin Data 7 iulie 2009 19:25:05
Problema Reguli Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
  
 #include <stdio.h>  
 #define max 1000002  
     
   long long v[500009];
   int k,q,sol,n, pi[max], t;  
   
   int vf (int x,int y)
   {int i;
    if (x<=n-y) return 0; else
		for (i=q+1;i<=n;i++) if (v[i]!=v[i-q]) {return 0; i=-1;break;}
		if (i!=-1) return 1;
		}
    
    int main()  
   {  
       freopen("reguli.in", "r", stdin);  
       freopen("reguli.out", "w", stdout);  
       scanf("%d", &n);  
       scanf("%d",&v[1]);  
	    for (q=2;q<=n;q++) {scanf("%d",&v[q]);v[q-1]=v[q]-v[q-1];}
		n--;  
	   k=0;sol=n;  
       pi[1]=0;  
       for (q=2; q<=n; q++)  
       {  
           while (k && v[k+1]!=v[q]) k=pi[k];  
           if (v[k+1]==v[q]) k++;  
           pi[q]=k;  
		   
          if (k && (q%(q-k)==0)&& vf(q-k,q)&& (q-k)<sol) sol=q-k;  
       }  
	      printf("%d\n", sol);
          for (q=1;q<=sol;q++) printf("%d\n",v[q]); 

       return 0;  
  }