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]).
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....
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(posxnegx) >= 1e7)
{
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]
#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(posxnegx) >= 1e7)
{
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]

 New poster
 Posts: 32
 Joined: Thu Jul 31, 2003 6:21 am
 Location: Daffodil Univ, Bangladesh
 Contact:
10341 Help please how to solve
How can i solve this problem? I tried in this way:
[c]
 CUT AFTER AC 
[/c]
[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!
Visit phpBB!
I've heard that there's someone solving this with NewtonRaphson 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?

 New poster
 Posts: 1
 Joined: Sun Feb 29, 2004 10:56 pm
 Contact:
[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)<1e20)//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
#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)<1e20)//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
 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
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...
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":
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
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:
These are a test set I've tried and my output:
What if the 4th decimal digit is 0? Should I print something like 0.7610 or .761 ?
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
Code: Select all
A subset of the one in the next message
Last edited by osoario on Wed Jun 22, 2005 3:26 pm, edited 1 time in total.
 Abednego
 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
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 < 1e14 instead of running 25 times.
I'm not sure who is right, but mine gets accepted. ;)
1. I don't have any special cases  just a binary search
2. The search terminates when dx < 1e14 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...
Thanks a lot!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 < 1e14 instead of running 25 times.
I'm not sure who is right, but mine gets accepted.
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
10341 wa
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....
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 (1E8)
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;
}
}
}
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?
Thanks in advance.
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
HomePage