UVA - 10014 - Simple calculations (经典的数学推导题!!)

UVA - 10014

Time Limit: 3000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu

id=19100" style="color:blue">Submit

 Status

Description

UVA - 10014 - Simple calculations     (经典的数学推导题!!)

id=19100" style="color:blue">The Problem

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.

The Input

id=19100" style="color:blue">The first line is the number of test cases, followed by a blank line.

id=19100" style="color:blue">For each test case, the first line of an input file 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.

Each test case will be separated by a single line.

The Output

For each test case, the output file should contain a1 in the same format as a0 and an+1.

id=19100" style="color:blue">Print a blank line between the outputs for two consecutive test cases.

Sample Input

1

1
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 :: 

option=com_onlinejudge&Itemid=8&category=395" style="color:blue">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\n", ans/(n+1));
if(cas!=0)printf("\n");
}
return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

上一篇:lintcode:被围绕的区域


下一篇:详解Adorner Layer(zz)