10341 - Solve It

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Thu Jul 17, 2003 7:58 am

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

User avatar
coolbila
New poster
Posts: 8
Joined: Tue Apr 01, 2003 8:11 pm

Post by coolbila » Fri Aug 15, 2003 11:22 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

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

WA.....

Post by mrtamtam » Sun Aug 17, 2003 12:54 pm

#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
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh
Contact:

10341 Help please how to solve

Post by Jewel of DIU » Mon Nov 03, 2003 10:04 am

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!

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Nov 17, 2003 3:52 pm

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

Cricital input :
0 0 0 0 0 0

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

Post by htl » Wed Jun 09, 2004 6:33 pm

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
New poster
Posts: 1
Joined: Sun Feb 29, 2004 10:56 pm
Contact:

Post by arash_cordi » Wed Nov 10, 2004 12:03 pm

[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

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sat Apr 23, 2005 10:37 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.
If only I had as much free time as I did in college...

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

Post by mf » Sun Apr 24, 2005 12:22 am

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

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun Apr 24, 2005 6:17 am

Thanks! That's exactly what the mistake was. That problem has some very nice input data.
If only I had as much free time as I did in college...

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

Post by osoario » Tue Jun 21, 2005 1:39 pm

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. :wink:
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.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Wed Jun 22, 2005 5:15 am

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. ;-)
If only I had as much free time as I did in college...

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

Post by osoario » Wed Jun 22, 2005 3:24 pm

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 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
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

10341 wa

Post by sunnycare » Mon Aug 22, 2005 1:07 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Sep 14, 2005 12:30 am

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.
Last edited by Jan on Wed Oct 25, 2006 12:37 am, edited 2 times in total.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 103 (10300-10399)”