poj 2601 Simple calculations

Simple calculations

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 6559		Accepted: 3291

Description

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₁.

Input

The first line of an input 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.

Output

The output file should contain a₁ in the same format as a₀ and a_n+1.

Sample Input

Sample Output

27.85

解题思路：

大概过程：

a[0]+a[2]-2a[1]-2c[1]=0

a[1]+a[3]-2a[2]-2c[2]=0

……

a[n-1] + a[n+1] - 2a[n] - 2c[n] = 0

累加可得：

a[0]+a[n+1]-a[1]-a[n]-2c[1]-2c[2]-...-2c[n]=0

依据a[n-1]+a[n+1]-2a[n]-2c[n]=0  => a[n+1]-2c[n]-a[n]=a[n]+2c[n]-a[n-1]

化简：a[0]+a[n]-a[1]-a[n-1]-2c[1]-2c[2]-...-2c[n-1]=0

同理：a[0]+a[n-1]-a[1]-a[n-2]-2c[1]-2c[2]-...-2c[n-2]=0

      ……

      a[0]+a[2]-a[1]-a[1]-2c[1]=0

相加上面各式可得n*a[0]+a[n+1]-(n+1)*a[1]-2*n*c[1]-2*(n-1)*c[2]-...-2*c[n]=0

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

#include <iostream>

#include <iomanip>

using namespace std;

#define MAX 3005

int main(){

	int n;

	double a0,an;

	double c[MAX];

	while (cin>>n){

		cin>>a0>>an;

		double ans=0;

		for (int i=0;i<n;i++){

			cin>>c[i];

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

		}

		ans=(n*a0+an-ans)/(n+1);

		cout<<fixed<<setprecision(2)<<ans<<endl;

	}

	return 0;

}

巴特西

poj 2601 Simple calculations

最新文章

热门文章