## 10341 - Solve It

Moderator: Board moderators

anupam vai,

i have solved this program condisdering there is only one unique (not same two or more) root of the given function between 1 and 0. i got AC here using bisection method.

now, would you tell me , if there would have two roots between 1.000 and 0.000, then the function give the same sign for both 1.00 and 0.000. In that case how can i solve that progam using bisection method? or how can i manage to get new limits accurately?

may be the given fuction had not two roots between 1 and 0 , as a matter i got AC. But if it would have, how can it be possible to solve ? for an example if y=f(x) function touches the x axis ie y=0. then the both side of the root show the same sign. ( ie. f(x+) * f(x-) >0 , [for the root x]).
__nOi.m....
Noim
Learning poster

Posts: 88
Joined: Sun Oct 13, 2002 6:11 am

I got wa many times and finally got AC because of the error set too big

WA
#define error 0.00001
...
while(right-left>error)
{
......
}

AC
#define error 0.00000001
....
while(right-left>error)
{
......
}
Oh my God ... Wrong Answer

coolbila
New poster

Posts: 8
Joined: Tue Apr 01, 2003 8:11 pm

### WA.....

#include <stdio.h>
#include <math.h>

int main()
{
int p,q,r,s,t,u;
double negx,posx,prex,x,incx=0.1;
int getneg,getpos;
int sol=0;

double f(double x)
{
return p*exp(-x)+q*sin(x)+r*cos(x)+s*tan(x)+t*x*x+u;
}

while (scanf("%d %d %d %d %d %d\n",&p,&q,&r,&s,&t,&u) > 0)
{
sol = 0;
incx = 0.0001;
getneg = 0;
getpos = 0;

if (f(0) * f(1) > 0)
{
puts("No solution");
continue;
}

if (f(0) > 0)
{
posx = 0;
negx = 1;
}
else
{
posx = 1;
negx = 0;
}

x = (negx + posx) / 2.0;
while (fabs(posx-negx) >= 1e-7)
{
if (f(x) < 0)
negx = x;
else
posx = x;
x = (negx + posx) / 2.0;

}

if (x <= 0.000001) x = 0;
else
if (x > 1) x = 1;

printf("%.4lf\n",x);
}

return 0;
}[c]

I have tried many times.... but still WA....
mrtamtam
New poster

Posts: 5
Joined: Wed Jan 15, 2003 9:50 pm

### 10341 Help please how to solve

How can i solve this problem? I tried in this way:
[c]
----------- CUT AFTER AC ---------------
[/c]
Last edited by Jewel of DIU on Sat Mar 20, 2004 3:57 pm, edited 1 time in total.
Hate WA
Visit phpBB!
Jewel of DIU
New poster

Posts: 32
Joined: Thu Jul 31, 2003 6:21 am

Your program does not give the correct answer for the 3rd sample input.

Cricital input :
0 0 0 0 0 0

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

I've heard that there's someone solving this with Newton-Raphson Method(or called Newton's Method, I think). But there are two things to think of, one is that f'(x) may be zero, the other is that we could get the 'root' out of the range [0,1]. Maybe there are some ways to overcome these problems. Could someone share your thought using nr method?
htl
Experienced poster

Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

[cpp]
#include <stdio.h>
#include <math.h>

int main()
{
int p,q,r,s,t,u,i;
double x,e,z;
while (scanf("%d %d %d %d %d %d",&p,&q,&r,&s,&t,&u)==6)
{
x = 1; //initial guess
e = 1;
for (i=0;i<8;i++)
{
z = -p*exp(-x)+q*cos(x)-r*sin(x)+s/(cos(x)*cos(x))+2*t*x; //f'
if (abs(z)<1e-20)//checking if f' is zero
{
printf("No solution\n");
goto exit;
}
e = -(p*exp(-x)+q*sin(x)+r*cos(x)+s*tan(x)+t*x*x+u)/z; // -f/f'
x += e; //next value for x
}
if (x>1 || x<0) //checking the range
printf("No solution\n");
else
printf("%.4lf\n",x);
exit:;
}
return 0;
}
[/cpp]

every thing seems to be ok for this code (i used newton method) with any critical input like "0 0 0 0 0 0"
but still getting WA
arash_cordi
New poster

Posts: 1
Joined: Sun Feb 29, 2004 10:56 pm

Could anyone tell me what is wrong with this code? It's just a simple binary search done twice to take care of both the increasing and the decreasing case. Thanks.

Code: Select all
`works now.`
Last edited by Abednego on Sun Apr 24, 2005 6:16 am, edited 1 time in total.
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

The value of x must belong to the range [0, 1], but your program sometimes prints values greater than 1.

For example, the output for all these test cases should be "No solution":
Code: Select all
`16 -1 12 -2 -12 44 -9 10 -2 -4 84 -15 19 0 -5 610 -5 20 -2 -11 416 -4 18 -7 -2 117 0 6 -8 -4 720 -3 5 -6 0 28 -7 18 -3 -12 10`
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

Thanks! That's exactly what the mistake was. That problem has some very nice input data.
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

I have a nice collection of Wrong Answers. I'm at that point when you start testing lots of strange things in your program (which contradict the terms of the problem trying to get an Accepted.
And I feel worse when I see that some people here had their programs accepted without realising that there can't be 2 cases (increasing/decreasing) because the coefficients p,q,r,s,t have such signs that the function is always decreasing in the interval.
The only expection is the case when these five coefficients are 0. Then there are no solution if u!=0, but if u is also zero all the numbers in [0,1] are solutions! Can someone tell me what the correct answer should be in this case (0,0,0,0,0,0)? My answer is 0.0000 but I have tried 1.000 and "No solution" too...

Here's my code:
Code: Select all
`Deleted after AC`

These are a test set I've tried and my output:

Code: Select all
`A subset of the one in the next message`

What if the 4th decimal digit is 0? Should I print something like 0.7610 or .761 ?
Last edited by osoario on Wed Jun 22, 2005 3:26 pm, edited 1 time in total.
osoario
New poster

Posts: 2
Joined: Mon Jun 20, 2005 10:08 pm
Location: Barcelona

I get the same answers. The differences between my solution and yours are
1. I don't have any special cases - just a binary search
2. The search terminates when dx < 1e-14 instead of running 25 times.
I'm not sure who is right, but mine gets accepted. ;-)
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

Abednego wrote:I get the same answers. The differences between my solution and yours are
1. I don't have any special cases - just a binary search
2. The search terminates when dx < 1e-14 instead of running 25 times.
I'm not sure who is right, but mine gets accepted.

Thanks a lot!
Well, I have had mine accepted.
It seems that the reason was that I was not writing the ending zeros of the solutions. I suppose it was obvious for a more experienced contestant, but...

Here is a set for testing with one of such cases, and the output produced by my accepted program:
Code: Select all
`0 0 0 0 -2 11 0 0 0 -1 21 -1 1 -1 -1 10 0 0 0 0 01 -20 3 -20 -5 62 -20 3 -20 -5 63 -20 3 -20 -5 64 -20 3 -20 -5 65 -20 3 -20 -5 66 -20 3 -20 -5 63 -4 1 -3 -2 56 -11 8 -20 -3 14 -4 4 -4 -4 517 -6 2 -8 -1 316 -1 12 -2 -12 44 -9 10 -2 -4 84 -15 19 0 -5 60.7071No solution0.75540.00000.23470.25210.26890.28500.30050.31540.78630.38070.80160.7628No solutionNo solutionNo solution`

The reason why I was doing the process just a number of times is that (while using the pure bisection method) the width of the remaining interval is always the correspondant power of 1/2, then waiting until dx<1e-14 is the same that waiting for 47 loops...
osoario
New poster

Posts: 2
Joined: Mon Jun 20, 2005 10:08 pm
Location: Barcelona

### 10341 wa

but i still get wa..

who can send me your accept code to me?
my mail is athena_kula@msn.com

i am confused about the "double" type data....

Code: Select all
`//10341 Solve It#include <iostream>#include <cmath>#define EPS (1E-8)using namespace std;long p,q,r,s,t,u;long double func(long double x){   return p*exp(-x)+q*sin(x)+r*cos(x)+s*tan(x)+t*x*x+u;}int main(int argc,char *argv[]){   cout.setf(ios::fixed,ios::floatfield);   cout.precision(4);   while(cin>>p)   {      cin>>q>>r>>s>>t>>u;      long double f1=func(1);      if(f1>EPS||(p+r+u<-EPS))      {                      cout<<"No solution\n";            continue;      }        if(p==0&&q==0&&r==0&&s==0&&t==0&&u==0)        {            cout<<"0.0000"<<endl;            continue;        }              else      {         long i;         long double xbeg,xend,xmid;         xbeg=0;         xend=1;         xmid=(xbeg+xend)/2;         for(i=1;i<=20;i++)         {             //cout<<"    "<<xmid<<endl;            if(func(xmid)>=0)               xbeg=xmid;            else               xend=xmid;            xmid=(xbeg+xend)/2;         }                     cout<<xmid<<endl;      }   }   }   `
sunnycare
Learning poster

Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

My code returns correct results for all the inputs I found on board. But I m still getting WA.

Here is my code. Can anyone help me?

Code: Select all
`Accepted :)`

Last edited by Jan on Wed Oct 25, 2006 12:37 am, edited 2 times in total.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm