Dãy số trung bình

Dãy số trung bình
Xét dãy số nguyên không giảm S1, S2, ..., Sn+1 (Si <= Si+1Dãy m1, m2, ...mn được xác định bởi công thức mi = (si + si+1)/2 (1<=i<=n) gọi là dãy trung bình của dãy S. Ở đây ta chỉ xét trường hợp mi là số nguyên. Cho trước dãy m, nhiệm vụ của bạn là tìm tất cả những dãy S nhận dãy m làm dãy trung bình
Input: Dữ liệu vào từ file Mean.inp gồm
     Dòng đầu tiên chứa số nguyên N (1<=N<=5 000 000)
     N dòng sau, dòng thứ i chứ số nguyên mi(1<=mi<=1 000 000 000)
Output: Dữ liệu ra ghi lên file Mean.out gồm một số nguyên duy nhất là số lượng dãy S thỏa yêu cầu đề bài mà bạn tìm được
Ràng buộc: Chương trình không được phép sử dụng quá 16MB bộ nhớ.
MEAN.INP
MEAN.OUT

3 2 5 9
4

Thuật toán: Từ công thức mi = (si + si+1)/2 ta có mi >= si. Bản chất của bài toán thật ra là yêu cầu ta tìm tập giá trị của s1 mà thôi vì khi có s1 ta có thể tính ra toàn bộ dãy s theo công thức của dãy m: si+1 = 2mi-1-si.
Đặt s1 = a, ta có s2 = 2m1 - a <= m2 <=> a>= 2m1 - m2.
s3 Tương tự, với các bất đẳng thức s4      a >= x
      a <= y
Gọi Xmaxlà giá trị lớn nhất trong số các cận dưới của a, Ymin là giá trị nhỏ nhất trong số các cận trên của A. Khi đó, dãy số S thỏa yêu cầu đề bài là Ymin - Xmax + 1. Độ phức tạp của thuật toán chỉ là O(n)!