UVA

UVA - 10014

Simple calculations

Time Limit: 3000MS

Memory Limit: Unknown

64bit IO Format: %lld & %llu

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

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 :: 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
", ans/(n+1));
		if(cas!=0)printf("
");
	}
	return 0;
}