UVA - 10014

Submit Status

Description

Simple calculations

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

The first line is the number of test cases, followed by a blank line.

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.

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;
} 

UVA - 10014 - Simple calculations （经典的数学推导题！！）

原文：http://blog.csdn.net/u014355480/article/details/42017347