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

UVA - 10014

Simple calculations

Time Limit: 3000MS

Memory Limit: Unknown

64bit IO Format: %lld & %llu

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

Status

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

50.50

25.50

10.15

Sample Output

27.85

Source

Root :: Prominent Problemsetters :: Alex Gevak

Root :: Competitive Programming 3: The New Lower Bound of Programming Contests (Steven & Felix Halim) :: Mathematics :: Ad Hoc Mathematics Problems :: Finding
Pattern or Formula, easier

Root :: Competitive Programming 2: This increases the lower bound of Programming Contests. Again (Steven & Felix Halim) :: Mathematics :: Ad Hoc Mathematics Problems ::

option=com_onlinejudge&Itemid=8&category=395" style="color:blue">Finding
Pattern or Formula

Root :: AOAPC I: Beginning Algorithm Contests (Rujia Liu) :: Volume 1. Elementary Problem Solving :: Maths - Misc

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

！

首先。依据题意有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;

}