10341 - Solve It

[Noim]

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]).

[coolbila]

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)
{
......
}

[mrtamtam]

#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....
please help[/c]

[Jewel of DIU]

How can i solve this problem? I tried in this way:
[c]
----------- CUT AFTER AC ---------------
[/c]

[sohel]

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

Cricital input :
0 0 0 0 0 0

[htl]

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?

[arash_cordi]

[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

[Abednego]

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.

[mf]

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 4
4 -9 10 -2 -4 8
4 -15 19 0 -5 6
10 -5 20 -2 -11 4
16 -4 18 -7 -2 1
17 0 6 -8 -4 7
20 -3 5 -6 0 2
8 -7 18 -3 -12 10

[Abednego]

Thanks! That's exactly what the mistake was. That problem has some very nice input data.

[osoario]

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 ?

[Abednego]

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. ;-)

[osoario]

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 1
1 0 0 0 -1 2
1 -1 1 -1 -1 1
0 0 0 0 0 0
1 -20 3 -20 -5 6
2 -20 3 -20 -5 6
3 -20 3 -20 -5 6
4 -20 3 -20 -5 6
5 -20 3 -20 -5 6
6 -20 3 -20 -5 6
3 -4 1 -3 -2 5
6 -11 8 -20 -3 1
4 -4 4 -4 -4 5
17 -6 2 -8 -1 3
16 -1 12 -2 -12 4
4 -9 10 -2 -4 8
4 -15 19 0 -5 6


0.7071
No solution
0.7554
0.0000
0.2347
0.2521
0.2689
0.2850
0.3005
0.3154
0.7863
0.3807
0.8016
0.7628
No solution
No solution
No 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...

[sunnycare]

i have searched all the topics about this problem ...
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;
		}
	}

	
}	

[Jan]

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

Thanks in advance.