Problem : 245 - Mean Sequence

Problem Statistics

Solved Member: 27　　Submission: 75　　User Tried: 27

Statement:

給定一個非遞減整數數列 s₁, ... , s_n+1 (s_i ≤ s_i+1，1 ≤ i ≤ n)，則由該數列所定義之中間數列 (mean sequence)為 m₁, ... , m_n，m_i=(s_i + s_i+1) / 2，1 ≤ i ≤ n。例如1, 2, 2, 4數列的中間值數列為1.5, 2, 3。請注意，雖然中間值數列中的值有可能是小數，但是在本題中，中間值數列的值都將是整數。

給定一個有n個整數的非遞減數列m₁, ... , m_n，請計算共有幾組n+1個整數的非遞減數列s₁, ... , s_n+1能產生該m₁, ... , m_n中間值數列。

Task:

請寫一個程式來：
•從標準輸入讀入一組非遞減整數數列。
•計算共有幾組非遞減數列其中間值數恰為上述非遞減整數數列。
•將答案輸出至標準輸出。

Input:Output:

輸入的第一行為一整數n ( 2 ≤ n ≤ 5000000 )。接下來的n行定義該m₁, ... , m_n數列，數列中的m_i ( 0 ≤ m_i ≤ 1 000 000 000 )出現在第i+1行。

你可以假設50%的測試資料中，n ≤ 1000且0 ≤ m_i ≤ 20000。

你的程式應該只輸出一個整數至標準輸出，即共有幾組非遞減數列可產生輸入資料中所給的中間值數列。

Sample Input:Sample Output:

3
2
5
9

Source:

IOI 2005

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	16384kb
1-1	1000ms	16384kb	5
1-2	1000ms	16384kb
2	1000ms	16384kb	5
3-1	1000ms	16384kb	5
3-2	1000ms	16384kb
4	1000ms	16384kb	5
5-1	1000ms	16384kb	5
5-2	1000ms	16384kb
6-1	1000ms	16384kb	5
6-2	1000ms	16384kb
7	1000ms	16384kb	5
8	1000ms	16384kb	5
9-1	1000ms	16384kb	5
9-2	1000ms	16384kb
10-1	1000ms	16384kb	5
10-2	1000ms	16384kb
11-1	5000ms	16384kb	5
11-2	5000ms	16384kb
12-1	5000ms	16384kb	5
12-2	5000ms	16384kb
13	5000ms	16384kb	5
14	5000ms	16384kb	5
15-1	5000ms	16384kb	5
15-2	5000ms	16384kb
16-1	5000ms	16384kb	5
16-2	5000ms	16384kb
17	5000ms	16384kb	5
18	5000ms	16384kb	5
19-1	5000ms	16384kb	5
19-2	5000ms	16384kb
20	5000ms	16384kb	5