Description

有一个包括n+2个元素的数列a0, a1, ..., an+1 (n <= 3000, -1000 <= ai <=1000)。它们之间满足ai = (ai-1 + ai+1)/2 - ci （i=1, 2, ..., n）。如今给出a0, an+1, c1, ... , cn.。请编敲代码计算出a1。

Input

输入的第一行是一个整数n。

接下去的两行各自是a0和an+1，（精确到小数点后两位）再接下去的n行是ci（精确到小数点后两位）。每一个数字占一行。

Output

输出a1 ，其格式与 a0 同样。

Sample Input

1

50.50

25.50

10.15

Sample Output

27.85

 

解题思路：

一開始想用递归来求，但是数据挺大的，n<=3000，所以便想找找当中的规律，看看能不能列出一个算式让a[1]用a[0]，a[n+1]和c[1～n]来表示。

首先能够列出下面算式：

2 * a[1] = a[0] + a[2] - 2 * c[1]

2 * a[2] = a[1] + a[3] - 2 * c[2]

......

2 * a[n] = a[n-1] + a[n+1] - 2 * c[n]

等式两边分别相加可得：

2 * (a[1] + ... + a[n]) = (a[0] + ... + a[n-1]) + (a[2] + ... + a[n+1]) - 2 * (c[1] + ... + c[n])

移项后得：

a[1] + a[n] = a[0] + a[n+1] - 2 * (c[1] + ... + c[n])

让下标n从1～ｎ,列出以上算式：

a[1] + a[1] = a[0] + a[2]

 - 2 * c[1]

a[1] + a[2] = a[0] + a[3] - 2 * (c[1] + c[2])

a[1] + a[n] = a[0] + a[n+1] - 2 * (c[1] + ... + c[n])

等式两边分别相加后得：

(n + 1) * a[1] = n * a[0] + a[n+1] - 2 * (c[1] + （c[1] + c[2]） + ... + （c[1] + c[2] + ... +c[n])） 

AC代码：

#include
      
       #define MAX_NUM 3005int main(){    double a[MAX_NUM], c[MAX_NUM];    int n;    scanf("%d", &n);    scanf("%lf%lf", &a[0], &a[n+1]);    for(int i = 1; i <= n; i++)        scanf("%lf", &c[i]);    int j = 1;    double sum_1 = 0, sum_2 = 0;    for(int i = 1; i <= n ; i++)    {        for(; j <= i; j++)        {            sum_1 += c[j];           }        sum_2 += sum_1;    }    a[1] = (n * a[0] + a[n + 1] - 2 * sum_2) / (n + 1);     printf("%.2lf\n", a[1]);    return 0;}