UVA - 10014

id=19100" style="color:blue">Submit

Description

Simple calculations

id=19100" style="color:blue">The Problem

There is a sequence of n+2 elements a₀, a₁,…, a_n+1 (n <= 3000; -1000 <=  a_i 1000). It is known that a_i = (a_i–1 + a_i+1)/2 – c_i   for each i=1, 2, ...,
n. You are given a₀, a_n+1, c₁, ... , c_n. Write a program which calculates a₁.

The Input

id=19100" style="color:blue">The first line is the number of test cases, followed by a blank line.

id=19100" style="color:blue">For each test case, the first line of an input file contains an integer n. The next two lines consist of numbers
a₀ and a_n+1 each having two digits after decimal point, and the next n lines contain numbers c_i (also with two digits after decimal point), one number per line.

Each test case will be separated by a single line.

The Output

For each test case, the output file should contain a₁ in the same format as a₀ and a_n+1.

id=19100" style="color:blue">Print a blank line between the outputs for two consecutive test cases.

Sample Input

1

1

50.50

25.50

10.15

Sample Output

27.85

Source

非常经典的数学推导题！！

！

首先。依据题意有a[i] = (a[i-1] + a[i+1]) / 2 - c[i];

变换可得a[i+1] = (a[i] + c[i]) * 2 - a[i-1];

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

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

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

= 4*a[n-2] - 3*a[n-3] + 6*c[n-2] + 4*c[n-1] + 2*c[n]

= 5*a[n-3] -
4*a[n-4] +
8*c[n-3] + 6*c[n-2] + 4*c[n-1] + 2*c[n]

....

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

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

手敲果然慢......

AC代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <string>

using namespace std;

const int maxn = 3005;

int main()

{

	int cas;

	scanf("%d", &cas);

	while(cas--)

	{

		int n;

		scanf("%d", &n);

		double a0, am, c[maxn];

		scanf("%lf %lf", &a0, &am);

		double ans = a0*n + am;

		for(int i=1; i<=n; i++)

		{

			scanf("%lf", &c[i]);

			ans -= (n+1-i)*c[i]*2;

		}

		printf("%.2lf\n", ans/(n+1));

		if(cas!=0)printf("\n");

	}

	return 0;

}