首页 > 代码库 > poj 2601 Simple calculations

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 a0, a1, ..., an+1 (n <= 3000, -1000 <= ai <=1000). It is known that ai = (ai-1 + ai+1)/2 - ci for each i=1, 2, ..., n. 
You are given a0, an+1, c1, ... , cn. Write a program which calculates a1.

Input

The first line of an input contains an integer n. The next two lines consist of numbers a0 and an+1 each having two digits after decimal point, and the next n lines contain numbers ci (also with two digits after decimal point), one number per line.

Output

The output file should contain a1 in the same format as a0 and an+1.

Sample Input

1
50.50
25.50
10.15

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