问题描述

Problem Description

有如下方程：Ai = (Ai-1 + Ai+1)/2 - Ci (i = 1, 2, 3, .... n).

若给出A0, An+1, 和 C1, C2, .....Cn.

请编程计算A1 = ?

Input

输入包括多个测试实例。

对于每个实例，首先是一个正整数n,(n <= 3000); 然后是2个数a0, an+1.接下来的n行每行有一个数ci(i = 1, ....n);输入以文件结束符结束。

Output

对于每个测试实例，用一行输出所求得的a1(保留2位小数).

Sample Input

1
50.00
25.00
10.00
2
50.00
25.00
10.00
20.00

Sample Output

27.50
15.00

问题分析

Problem Analyse

公式推导

Algorithm Analyse

Ai = (Ai-1 + Ai+1)/2 - Ci (i = 1, 2, 3, .... n)。用A5做示范，就能猜测出公式来。证明方法可以采用数学归纳法。这里证明从略。

A₅ = (A₄ + A₆) / 2 - C₅

A₄ = (A₃ + A₅) / 2 - C₄ = A₃ / 2 + A₄ / 4 + A₆ / 4 - C₅ / 2 - C₄ => A₄ = 2A₃/3 + A₆/3 - 2C₅/3 - 4C₄/3

A₃ = (A₂ + A₄) / 2 - C₃ = A₂ / 2 + A₃ / 3 + A₆ / 6 - C₅ / 3 - 2C₄ / 3 - C₃ => A₃ = 3A₂/4 + A₆/4 - C₅/2 - C₄ - 3C₃/2

A₂ = (A₁ + A₃) / 2 - C₂ = A₁ / 2 + 3A₂ / 8 + A₆ / 8 - C₅ / 4 - C₄ / 2 - 3C₃ / 4 - C₂ => A₂ = 4A₁/5 + A₆/5 - 2C₅/5 - 4C₄/5 - 6C₃/5 - 8C₂/5

A₁ = (A₀ + A₂) / 2 - C₁ = A₀ / 2 + 2A₁ / 5 + A₆ / 10 - C₅ / 5 - 2C₄ / 5 - 3C₃ / 5 - 4C₂ / 5 - C₁ => A₁ = 5A₀/6 + A₆/6 - C₅/3 - 2C₄/3 - C₃ - 4C₂/3 - 5C₁/3

算到这里，我想你已经总结出公式了：A1 = (n * A₀ + A_n+1 - 2 * C_n - 4 * C_n-1 - ... - 2 * i * C_n-i+1 - 2 * n * C₁) / (n + 1)

参考源码