IOI '05 Mean Sequence

這題被小乃瞬秒XD    不過其實還頗有趣的                                                                                                         .


Description:

定義一個數列S的Mean序列M:

Mi = (Si + S(i+1))/2

例如   序列1, 1, 3, 5, 15的M為: 1, 2, 4, 10



給你一個有n項的序列M，請問有多少S使得

1. S的Mean序列為M

2. S1 <= S2 <= S3 <= ... <= S(n+1)


n<= 5,000,000







Solution:

M2-M1 = (S3-S1)/2

依此，可以把奇數項和偶數項分開討論，例如範例就變成

(a), (b), (a+2), (b+4), (a+14)

再由條件2.

(a)<= (b)<= (a+2)<= (b+4)<= (a+14)

解不等式  加上a+b = 2(M1)驗證


總複雜度O(n)