ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1047. Simple Calculations

The Mathematical method and its derivation
Posted by jagatsastry 1 Dec 2007 02:43
Well people, the formula i have used is
........................................................... n
..................... (A[n+1] - A[0] - 2 * Sigma((n - k + 1) * c[k]))
......................................................... k=1
A[1] = A[0] + ---------------------------------------------
...................................................... n + 1

DERIVATION:
The derivation is as follows

given a[i]=(a[i-1]+a[i+1])/2-c[i] for i=1,2,3...n
->2a[i]=a[i-1]+a[i+1]-2c[i]
->a[i]-a[i-1]=a[i+1]-a[i]-2c[i]


Assume difference variables d[1..n+1] where d[i]=a[i]-a[i-1]

From above  we have
d[i]=d[i+1]-2c[i]

hence d[i+1]=d[i]+2c[i]

We need to find d1 (a1-a0)
from d[n+1]=d1+2*sigma[i=1..n](c[i])

We get a[n+1]-a[0]=d1+sigma[i=2..n+1](d[i])
->d1+sigma[i=2..n+1](d1+2*sigma[j=1..i-1](c[j])
->(n+1)d1+2*(c[1]+(c[1]+c[2])+(c[1]+c[2]+c[3]).....(c[1]+...c[n]))
->(n+1)d1+2*sigma[i=1..n]((n-i+1)*c[i])

Hence
d1=(a[n+1]-a0-a*sigma[i=1..n]((n-i+1)*c[i]))/(n+1)

Finally the required a1 is
a1=a0+(a[n+1]-a0-2*sigma[i=1..n]((n-i+1)*c[i])/(n+1))


........................................................... n
..................... (A[n+1] - A[0] - 2 * Sigma((n - k + 1) * c[k]))
......................................................... k=1
A[1] = A[0] + ---------------------------------------------
...................................................... n + 1


IMPLEMENTATION:
The way i have implemented it is

    double sigma=0;
    for(int i=1;i<=n;i++)
    {
        sigma+=(n-i+1)*c[i-1];
    }
    double a1=a0+(an1-a0-2*sigma)/(n+1); //is the reqd ans

Where c[0] stores c1, c[1] stores c2 and so on.
a0, an1 are the given values

Regards,
Jagat. ( http://jagatsastry.blogspot.com )


Edited by author 03.12.2007 00:15
Re: The Mathematical method and its derivation
Posted by Meirambek 10 Jun 2011 21:13
vot ty tupoi....mog bi tupo formulu vstavit'!!!