Cod sursa(job #196748)

Utilizator cipPaduraru Ciprian - Ionut cip Data 28 iunie 2008 17:29:54
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstring>
#include <cstdio>

#define MAX_N	500001

int Dif[MAX_N],N,K[MAX_N];

void load()
{
	scanf("%d",&N);
	int actual,precedent;
	scanf("%d",&precedent);

	for (int i = 1 ; i < N ; i++)
	{
		scanf("%d",&actual);
		Dif[i] = actual - precedent;
		precedent = actual;
	}
	N--;
}

void prefix()
{
	int i, q  = 0;
	
	for (i = 2, K[1] = 0 ; i <= N; i++)
	{
		while(q && Dif[q+1] != Dif[i])
			q = K[q];

		if (Dif[q+1] == Dif[i])
			++q;
		K[i] = q;
	}
}

void solve()
{
	int iMinLength = N;
	
	//try all lengths
	for (int L = N - 1  ; L > 0 ;L--)
	{
		int C = N / L;
		int R = N % L;

		int length = N - R - K[N-R];

		if ( (K[N-R] > 0)  && (L == length) && ( N - R)%L == 0 && K[N] == (K[N-R] + R))
			iMinLength = L;
	}

	printf("%d\n",iMinLength);
	for (int i = 1 ; i <= iMinLength;i++)
		printf("%d\n",Dif[i]);
}

int main(int argc, char *argv[])
{
	freopen("reguli.in","r",stdin);
	freopen("reguli.out","w",stdout);

	load();
	prefix();
	solve();

	return 0;
}