Cod sursa(job #1007162)

Utilizator andreiiiiPopa Andrei andreiiii Data 8 octombrie 2013 14:05:09
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <cstdio>
#define N 500002
using namespace std;

int a[N], pi[N];
int n;

int verif(int i)
{
	if(!pi[i]||i%(i-pi[i])!=0) return 0;
	int k=n;
	while(k)
	{
		if(pi[k]==n-i) return 1;
		k=pi[k];
	}
	return 0;
}

int main()
{
	freopen("reguli.in", "r", stdin);
	freopen("reguli.out", "w", stdout);
	int i, x, y, k=0, sol;
	scanf("%d%d", &n, &x);
	n--;
	for(i=1;i<=n;i++)
	{
		scanf("%d", &y);
		a[i]=y-x;
		x=y;
	}
	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;
	}
	for(i=1;i<=n;i++)
	{
		if(verif(i)&&i-pi[i]<sol)
		{
			sol=i-pi[i];
		}
	}
	printf("%d\n", sol);
	for(i=1;i<=sol;i++)
	{
		printf("%d\n", a[i]);
	}
}