Cod sursa(job #93623)

Utilizator girl_styleBianca Boeriu girl_style Data 19 octombrie 2007 17:21:36
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//using namespace std;

long n,a[500000],p[500000];

void citire(){
   long i,x,y;
   freopen("reguli.in","r",stdin);
   scanf("%d",&n);
   scanf("%d",&x);
   for (long i=2; i<=n; i++){
     scanf("%d",&y);
	 a[i-1]=y-x;
	 x=y;
   }
   fclose(stdin);
   n=n-1;
}

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

bool ok(long r){
	long i;
	for (long i=1; i<=r; i++){
		if (a[i]!=a[n-r+i]){
			return false;
		}
	}
	return true;
}

void afis(long l){
	long i;
	printf("%d\n",l);
	for (long i=1; i<=l; i++)
		printf("%d\n",a[i]);
}

void secv(){
	long l,r,c;
	for (long l=1; l<=n; l++){
		r=n%l;
		c=n/l;
		if ((p[n-r]>0) && ((n-r)%(n-r-p[n-r])==0) &&
			((n-r)/(n-r-p[n-r])==c) && (ok(r)==true)){
				afis(l);
				return;
		}
	}
}

void main(){
  freopen("reguli.out","w",stdout);
  citire();
  prefix();
  secv();
  fclose(stdout);
}