Cod sursa(job #466579)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 27 iunie 2010 11:07:45
Problema Numarare Scor 10
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 0.88 kb
#include<cstdio>
#define infile "numarare.in"
#define outfile "numarare.out"
#define nmax 100013

using namespace std;
int v[nmax]; //vectorul cu numerele
int d[nmax]; //d[i]=v[i]-v[i-1]
int l[nmax]; //l[i]=cate elemente pe pozitii consecutive (inainte) sunt egale cu d[i]
int n; //numarul de numere
long long count; //numarul de secvente

void read()
{
	int i;
	scanf("%d\n",&n);
	for(i=1;i<=n;++i)
		scanf("%d",&v[i]);
}

void init()
{
	int i;
	
	//construim pe d
	for(i=2;i<=n;++i)
		d[i]=v[i]-v[i-1];

	//construim pe l
	for(i=2;i<=n;++i)
		if(d[i]==d[i-1])
			l[i]=l[i-1]+1;
		else l[i]=1;
}

void solve()
{
	int i;

	//incercam sa numaram solutiile
	for(i=2;i<=n;i++)
		count+=(l[i]+1)>>1;
}

void write()
{
	printf("%lld\n",count);
}

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

	read();
	init();
	solve();
	write();

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