Текущ брой на Списание ИнфоМан
 


Международна олимпиада по информатика 2005, Задача 1.2. MEAN SEQUENCE

Уловието на задачата може да прочетете тук.

Решение

Решението на задачата се базира на следния факт: ако е определена редица M = m1,m2,…,mn и е фиксиран някой елементsi от редицата S = s1, s2,…,sn+1, и ако M е средна редица на S, то може еднозначно да се определят всички елементи на S. Например нека

M = 2,4,6

ие фиксирано s2= 3, то последователно получаваме s1 = 1, s3 = 5, s4 = 7.

Ще наричаме дадена стойност v“валидна” за елементаsiако за si = v съществува редица s1, s2,…,sn+1, чиято средна е m1,m2,…,mn. Ако aи b са валидни стойности за елементаsi, то и всяко c, за което аcb, e валидна стойност.

Разглеждаме редицата s1, s2,…,sn+1със средна редица m1,m2,…,mnи е пресметнат интервала от валидни стойности за sn+1. Ако се добави елемент mn+1, то ще се промени интервала за sn+1и ще се добави елемент sn+2. Нека за всеки елемент siдолната граница от валидни стойности е lsi, а горната – usi. Интервалите за елементите от редицата s1, s2,…,sn+1могат да се изчислят отляво надясно. В началото стойността ls1е минус безкрайности us1е плюс безкрайност. След това, за да се пресметнат lsi и usiза дадено iсе използват стойностите за i-1.

Нека е дефинирана функцията r(a,b) по следния начин:

r(a,b) = c, ако ½*(a+c) = b, тоест r(a,b) = 2*b-a

Разглеждаме елементите на M отляво надясно и в момента обработваме елементаmi. Понеже редицата S по условие трябва да е ненамаляваща, то елементътsi не може да бъде по-голям от mi. Така получаваме:

usi = min(usi, mi)

Използвайки така пресметнатите стойности lsi и usiи свойството на средната редица, че mi =(si+si+1)/2 се получават следните стойности заlsi+1 и usi+1:

lsi+1 = r(usi, mi), usi+1 = r(lsi, mi)

Така с линейна сложност се получава интервалът[lsn+1,usn+1]за последния елемент на редицата S. Броят Cна ненамаляващите редици, на които M е средна, е точно равен на големината на този интервал, тоест:

C = usn+ 1 - lsn+1 + 1.

Примерна реализация


#include <stdio.h>

#define INF			1000000010

int n;
int lb1,ub1,lb2,ub2;
int ans;

void solve()
{
	int i;
	int ib;

	lb1 = -INF;
	ub1 = INF;

	scanf("%d",&n);

	for(i=0;i<n;i++)
	{
		scanf("%d",&ib);

		if(ub1>ib)	// if needed update the upper bound
			ub1 = ib;

		lb2 = 2*ib-ub1;	// calculate the bounds for the next number
		ub2 = 2*ib-lb1;	// using the bounds for the previous

		lb1 = lb2;
		ub1 = ub2;
	}

	ans = ub1 - lb1 + 1;
	if(ans<0) ans = 0;
}

void output()
{
	printf("%d\n",ans);
}

int main()
{
	solve();
	output();

	return 0;
}

Автор: Антон Димитров


обратно към брой 27