北大 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)

代码

#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;
}