Cod sursa(job #273798)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 9 martie 2009 00:24:14
Problema Reguli Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<stdio.h>
#define infile "reguli.in"
#define outfile "reguli.out"
#define nmax 500*1001
long long x[nmax]; //sirul cu numere
long long d[nmax]; //d[i]=x[i]-x[i-1]
int p[nmax]; //prefixul vectorului d
int n; //lungimea sirului

void citire()
	{
	int i;
	scanf("%d",&n); //numarul de elemente din sir
	for(i=0;i<n;i++)
		scanf("%lld",&x[i]); //citim elementul
	}

void diferente()
	{
	int i;
	for(i=1;i<n;i++)
		d[i]=x[i]-x[i-1]; //calculam vectorul pentru diferentele dintre elementele lui x pe pozitii vecine
	}

void prefix()
	{
	int i,k=0;
	p[0]=0; //cu o pozitie mai putin decat pozitia ce trebuie comparata
	for(i=2;i<n;i++)
		{
		while(k>0&&d[i]!=d[k+1]) k=p[k]; //cat timp nu poate sa continue
		if(d[i]==d[k+1]) k++; //poate sa continue
		p[i]=k; //pozitia ce poate sa fie continuata
		}
	}

void afisare()
	{
	int i,j;
	for(i=n-1;p[i];i--); //cautam pozitia ultimului 0
	printf("%d\n",i); //afisem lungimea minima a sirului a (cel din problema)
	for(j=1;j<=i;j++)
		printf("%lld\n",d[j]); //afisem sirul
	}

int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire();
diferente();
prefix();
afisare();

fclose(stdin);
fclose(stdout);
return 0;
}