Международна олимпиада по информатика 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, за
което а≤c≤b, 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
|