北大 acm 2601 Simple calculations 解题报告

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4491 Accepted: 2325

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

150.5025.5010.15

Sample Output

27.85

由公式ai = (ai-1 + ai+1)/2 - ci ; 给出 a0 an+1 和 c1,c2,c3……ci,求出a1 方法: 2ai = ai-1 + ai+1 - 2ci ; 2ai-1 = ai-2 + ai - 2ci-1 ; 2ai-2 = ai-3 + ai-1 - 2ci-2 ; . . . . . . . . . . . . 2a1 = a0 + a2 - 2c1 ;相加得出: ai+1 - a1 = ai- a0 + 2(c1+c2+c3+….+ci)转化:
ai+1 - ai = a1- a0 + 2(c1+c2+c3+…………..+ci) ai - ai-1 = a1- a0 + 2(c1+c2+c3+……….+ci-1) ai-1 - ai-2 = a1- a0 + 2(c1+c2+c3+….+ci-2) . . . . . . . . . . . . . . . . .. . . . . a2 - a1 = a1- a0 + 2c1相加化简得: ai+1 - a1= a1- a0 +2( nc1 + (n-1)c2 + (n-2)c3 +…..+2cn-1+cn )
化简得: a1=(ai+1 +na0-2( nc1 + (n-1)
c2 + (n-2)c3 +…..+2cn-1+cn ))/(n+1)

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
int main()
{
float a0,ak,c[4000],a1,sumc;
int n,i; while(cin>>n)
{
sumc=0;
cin>>a0;
cin>>ak;
for(i=1;i<=n;i++)
{
cin>>c[i];
sumc+=2*(n+1-i)*c[i];
}
a1=(ak+n*a0-sumc)/(n+1);
printf("%.2f\n",a1);
}
return 0;
}