Cod sursa(job #309926)

Utilizator FlorianFlorian Marcu Florian Data 1 mai 2009 14:08:31
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<cstdio>
using namespace std;
#define MAX_N 500003
long long unsigned A[MAX_N];
int pi[MAX_N];
bool ok[MAX_N];
int N;
void read()
{
	freopen("reguli.in","r",stdin);
	freopen("reguli.out","w",stdout);
	scanf("%d",&N);
	long long unsigned cr, ant;
	int i;
	scanf("%llu",&ant);
	--N;
	for(i=1;i<=N;++i)
	{
		scanf("%llu",&cr);
		A[i] = cr - ant;
		ant = cr;
	}
}
void make_prefix()
{
	int i,k;
	pi[1] = 0; k = 0;
	for(i=2;i<=N;++i)
	{
		while(k && A[k+1] != A[i]) k = pi[k];
		if(A[k+1] == A[i]) ++k;
		pi[i] = k;
	}
}
void make_ok()
{
	int k = N;
	ok[0] = true;
	while(k)
	{
		ok[k] = 1;
		k = pi[k];
	}
}
void solve()
{
	int c,r;
	int L,i;
	for(L = 1; L <= N; ++ L)
	{
		r = N % L; c = N / L;
		if(pi[N-r] == 0) continue;
		if( (N-r) % ( N - r - pi[N-r] ) ) continue;
		if( (N-r) / ( N - r - pi[N-r]) != c) continue;
		if(!ok[r]) continue;
		printf("%d\n",L);
		break;
	}
	if(L == N+1) { L = N; printf("%d\n",N); }
	for(i=1;i<=L;++i) printf("%d\n",A[i]);
}
int main()
{
	read();
	make_prefix();
	make_ok();
	solve();
	return 0;
}