首页 > 代码库 > hdu 2086 A1 = ?

hdu 2086 A1 = ?

A1 = ?

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4682    Accepted Submission(s): 2990


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

 

分析:

公式推导

A5 = (A4 + A6) / 2 - C5

A4 = (A3 + A5) / 2 - C4 = A3 / 2 + A4 / 4 + A6 / 4 - C5 / 2 - C4
=>A4 = 2A3/3 + A6/3 - 2C5/3 - 4C4/3

A3 = (A2 + A4) / 2 - C3 = A2 / 2 + A3 / 3 + A6 / 6 - C5 / 3 - 2C4 / 3 - C3
=>A3 = 3A2/4 + A6/4 - C5/2 - C4 - 3C3/2

A2 = (A1 + A3) / 2 - C2 = A1 / 2 + 3A2 / 8 + A6 / 8 - C5 / 4 - C4 / 2 - 3C3 / 4 - C2
=>A2 = 4A1/5 + A6/5 - 2C5/5 - 4C4/5 - 6C3/5 - 8C2/5

A1 = (A0 + A2) / 2 - C1 = A0 / 2 + 2A1 / 5 + A6 / 10 - C5 / 5 - 2C4 / 5 - 3C3 / 5 - 4C2 / 5 - C1
=>A1 = 5A0/6 + A6/6 - C5/3 - 2C4/3 - C3 - 4C2/3 - 5C1/3

算到这里,我想你已经总结出公式了:
A1 = (n * A0 + An+1 - 2 * Cn - 4 * Cn-1 - ... - 2 * i * Cn-i+1 - 2 * n * C1) / (n + 1)

 

<span style="font-size:18px;">#include<stdio.h>
int main ()
{
  int t,i;
  double a,b,c[10000],d;
  while (~scanf("%d",&t))
  {
    scanf("%lf%lf",&a,&b);
	for(i=1;i<=t;i++)
		scanf("%lf",&c[i]);
    d=t*a+b;
	for(i=1;i<=t;i++)
       d-=2*i*c[t-i+1];
	printf("%.2lf\n",d/(t+1));
  }
  return 0;
}</span>