Hello guys
in this problem we have n equation with n unknown
than solved with Gause-Jordan modification
a0 a1 a2 a3 a4 a5 .... an
if a1=(a0+a2)/2 - c0 then
2a1 - a2 = a0- 2c0
if a2=(a1+a3)/2 - c1 then
-a1 +2a2 - a3= -2c1
....
2a1 - a2     = a0- 2c1
-a1 +2a2 - a3= -2c2
-a2 +2a3 - a4= -2c3
-a3 +2a4 - a5= -2c4
....
-an +2an-1 - an+1 = -2cn
e.g for n=5:
2  -1   0   0   0   a0-2c1
-1  2   -1  0   0   -2c2
0   -1  2   -1  0   -2c3
0   0   -1  2   -1  -2c4
0   0   0   -1  2   a6-2c5
and now you must solve the top diagonal "-1" of
matirs ( start of last row)and finish.
the order is O(n)
sudo code is:
m[0 ... n]
a=2;
while(--n){
 f= 1/a;
 m[n-1]= m[n-1]+ f*m[n];
 a = 2-f;
}
cout<< m[0]/a ;


Edited by author 01.03.2008 22:56

I had WA2 with std::cout and round|trunc|floor functions. Then I used printf("%.2f", result) and got WA4. What's going on with output requirements?

I bruteforced for all integers in range(-2000,2000) and got the best approximation for value a1. Then I brutforced for all doubles in range(a1-100;a1+100) and got AC

Considered several ways
Decided binary search is the best

n = 0 ?
Может такое быть ?

In the problem statement there isn't any info about C[i]. Coubld it be negative or all of input numbers are positive?

Дайте, пожалуйста, подсказку...

My AC solution doesn't use any cool algorithmes; just one formula.

3 - diagonal initial matrix

Edited by author 23.08.2011 20:36

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

What Does CRASH mean?

and why is there WA on 7 test?

Hi all!

I used Binary Search to solve this problem (because I'm not good at Math) and got AC after WA#2 3 times.

For getting AC, I changed my print line from:

cout << result << endl;
// or print("%f\n", result);

To:

print("%.2f\n", result);

It means you must format your result with 2 precisions after the decimal point, or your result will be something like: 14.99038461538461538461538461538462 (many number after the decimal point).

I hope this would help.
Please reply and notice me if there is something wrong.

MitRo.

Edited by author 10.06.2010 10:43

Edited by author 10.06.2010 10:43

Anybody use this? It's right formula or no?

a1:=(n*a(0)+a(n+1)-sum(i=1 to n+1 , c(i)*2^i))/(n+1)   ?

Edited by author 31.10.2009 19:00

a[n+1]-a[n]=a[1]-a[0]+2*(c[1]+c[2]+...+c[n]);

code:

#include<stdio.h>

#define N 3000
float c[N+5];

int main()
{
    int i,k,m;
    float sum,a0,an,t;
    scanf("%d",&m);
    scanf("%f%f",&a0,&an);
    for(i=1;i<=m;i++)
      scanf("%f",&c[i]);
    sum=0;
    k=m;
    for(i=1;i<=m;i++)
    {
        sum=sum+k*c[i];
        k--;
    }
    sum=sum*2;
    t=(an+m*a0-sum)/(m+1);
    printf("%.2f",t);
    return 0;
}


Edited by author 14.05.2010 19:53

I found my stupid mistake!

need have only one:
#include <cmath>

Edited by author 30.04.2010 02:30

It's my AC solution. I hope it will help you...
Idea: binary searching a[1]. Be carefull with epsilons!


#include<iostream>
#include<cmath>
using namespace std;
int N;
const double eps=1e-9;
double a[3010],c[3010],x;
void solve()
{
for(int i=2;i<=N;i++)a[i]=2*(a[i-1]+c[i-1])-a[i-2];
x=2*(a[N]+c[N])-a[N-1];
}
int main()
{
scanf("%d",&N);
scanf("%lf%lf",&a[0],&a[N+1]);
for(int i=1;i<=N;i++)cin>>c[i];
double l=-2000.000,r=2000.00;
while(l-r<eps)
{
double mid=(l+r)/2.0;
a[1]=mid;
solve();
if(fabs(a[N+1]-x)<eps){printf("%.2lf\n",mid);break;}
else if(a[N+1]-x<eps)r=mid;else l=mid;
}
system("pause");
return 0;
}

#include <iostream>
using namespace std;
int main()
{
    int n;
    double head,tail;
    cin>>n>>head>>tail;
    double * c =new double[n];
    int i=0;
    while(i!=n)
    {
        cin>>c[i];
        i++;
    }
    double csum=0;
    for(int j=0;j<n;j++)
    csum+=(n-j)*c[j];

    double a1;
    a1=(head+n*tail-2*csum)/(n+1);
    printf("%2.2f",a1);
    return 0;
}

my mistake,head and tail should be swapped!



Edited by author 09.10.2008 23:14

first,I used float in c,but WA;
then i changed it into double and got passed;
but the float type has 7 valid digit and only 2 needed,who knows why?