Cod sursa(job #1202067)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 26 iunie 2014 19:42:06
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>
#define min(a,b) a<b?a:b

int N,i,prefix[500010],sol,r;
long long x,A[500010],a;

void compute()
{
	int q = 0;
	for(int i = 2;i < N;i++)
	{
		while(q > 0 && A[q+1]!=A[i]) q = prefix[q];
		if(A[q+1] == A[i])q++;
		prefix[i] = q;
	}
}

int main()
{
	freopen("reguli.in","r",stdin);
	freopen("reguli.out","w",stdout);
	scanf("%d",&N);
	scanf("%lld",&x);
	for(i=1;i<N;i++)
	{
		scanf("%lld",&a);
		A[i] = a - x;
		x = a;
	}
	compute();
	sol = N-1;
	for(i=N-2;i>=2;i--)
	{
		r = N-i-1;
		if(prefix[N-1] < r)continue;
		sol = min(sol,i);
		if(prefix[i] == 0)continue;
		if(i%(i-prefix[i]) == 0)sol = min(sol,i - prefix[i]);
	}
	printf("%d\n",sol);
	for(i=1;i<=sol;i++)printf("%d\n",A[i]);
	return 0;
}