Page 3 of 5
Posted: Wed Sep 14, 2005 5:31 am
by mf
Input:
Code: Select all
16 -1 9 -11 -14 18
11 -18 11 -7 -6 16
12 -3 1 -4 -18 19
12 -2 10 -3 -8 1
6 -15 11 -19 -7 -13
9 -7 10 0 -4 -1
15 -1 18 -8 -7 5
20 -6 6 -12 -18 -14
5 -5 3 -10 -15 -1
12 -15 18 -9 -4 -19
Output:
Code: Select all
0.9580
0.8911
0.9489
0.9074
0.0976
0.9066
0.9991
0.2879
0.2879
0.2879
Posted: Wed Sep 14, 2005 6:35 am
by Jan
Thanks mf. Your inputs are great. I have changed my code. But still WA.

.
Posted: Wed Sep 14, 2005 8:31 am
by mf
Try using a power of 2 for your variable m, increase constant 100000, or just use a diffrent algorithm e.g. bisection.
Btw, the function is always non-increasing under given constraints, so there's no need to consider two cases.
Posted: Wed Sep 14, 2005 8:52 am
by Jan
Thanks for your reply. But why this method is wrong....??
I have tried two possibilities. But if there is one possibility then why I will get WA.
In fact this method is quite faster. And again if we use m^2 there will we no change in the output. And I have tried many inputs, but got no errors.
Any tricky cases?? ....
Can anyone help?
Thanks.
Posted: Wed Sep 14, 2005 9:55 am
by mf
Try this test case: 0 0 0 0 -1 1.
Posted: Wed Sep 14, 2005 6:16 pm
by Jan
My code returns ...
Output:
Still found no error....

Posted: Wed Sep 14, 2005 11:47 pm
by mf
On my computer your program prints 0.0000 for that test.
Posted: Thu Sep 15, 2005 10:41 am
by Jan
Thanks mf

.
Finally I got my error. My compiler returns 1 where yours doesnot. You made two conditions...
Code: Select all
.....
else if (-eps < x1 && x1 < eps)
printf("0.0000\n");
else if (-eps < x2 && x2 < eps)
printf("1.0000\n");
.....
I added these conditions and got my code Accepted. Thank u again. I was really stuck in this problem.
And don't forget to delete the code...

Posted: Fri Sep 16, 2005 11:42 pm
by baleezo
Could anyone tell me what is wrong with my code? It's just a simple binary search to take care of both the increasing and the decreasing case. Thanks a lot.
Posted: Sat Sep 17, 2005 11:12 pm
by Jan
Use the algorithm.
Code: Select all
1. calculate x=f(0) and y=f(1)
2. if (x > 0 && y > 0) print 'No solution'.
3. if (x < 0 && y < 0) print 'No solution'.
4. if ( x == 0 ) print '0.0000'.
5. if ( y == 0 ) print '1.0000'.
6. You are sure that u have a solution, and calculate it (by your process).
For checking the floating point numbers try to use epsilon.
Code: Select all
Suppose
eps = 0.00000000001
use....
(x > eps) instead of (x > 0)
(x < -eps) instead of (x < 0)
(x > -eps && x < eps) instead of (x == 0)
And the function is strictly increasing. So, no need to calculate decreasing part.
Hope these help you.
Posted: Sun Sep 18, 2005 7:38 pm
by baleezo
Thanks for your reply. I have changed my code like this but still WA...
And I have tried all the test data in this thread
10341
Posted: Tue Oct 04, 2005 5:53 pm
by vardiar
what about this one
//the record 43 WA!!!!!
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
long double f1(long double p,long double q,long double r,long double s,long double t
,long double u,long double x)
{
return ( p*exp(-1*x)+ q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u );
}
/*long double f(long double p,long double q,long double r,long double s,long double t
,long double u,long double a
,long double b)
{
return (b-(((b-a)*f1(p,q,r,s,t,u,b))/(f1(p,q,r,s,t,u,b)-f1(p,q,r,s,t,u,a))));
}*/
void main()
{
int p1,q1,r1,s1,t1,u1;
long double a=0,b=1,c=0;
int g=0;
while(cin>>p1>>q1>>r1>>s1>>t1>>u1)
{
g=0;
long double p=p1,q=q1,r=r1,s=s1,t=t1,u=u1;
a=0;
b=1;
c=0;
long double f1a,f1b,f1c,c1=999999999;
f1a=f1(p,q,r,s,t,u,a);
f1b=f1(p,q,r,s,t,u,b);
while(1)
{
//f1a=f1(p,q,r,s,t,u,a);
//f1b=f1(p,q,r,s,t,u,b);
if(f1a*f1b>0)
{
cout<<"No solution"<<endl;
break;
}
if(f1a==0)
{
//a+=0.005;
printf("%.4f\n",a);
g=0;
break;
}
if(f1b==0)
{
//b+=0.005;
printf("%.4f\n",b);
g=0;
break;
}
//c=f(p,q,r,s,t,u,a,b);
//c1=c;
c=(b+a)/2;
f1c=f1(p,q,r,s,t,u,c);
if(f1a*f1c<0)
{
b=c;
f1b=f1c;
}
if(f1b*f1c<0)
{
a=c;
f1a=f1c;
}
//f1c=f1(p,q,r,s,t,u,c);
if(f1c==0 ||abs(f1c-c1)<0.00001)
{
//c+=0.005;
printf("%.4f\n",c);
g=0;
break;
}
c1=f1c;
g++;
}
}
}[/code]
Posted: Tue Dec 27, 2005 3:43 am
by daveon
Is it just my computer or is your program not even passing the sample input?
10341(solve it)
Posted: Thu Feb 23, 2006 11:38 pm
by serur
Fellows,
what can be wrong with yhe standard "dividing-by-two" algorithm applied to the problem 10341? I still have WA, though this method applied to other similiar problems accepted.
Or rather would you mind sharing with me your source code for this problem if it got accepted?
10341
Posted: Thu Feb 23, 2006 11:48 pm
by serur
on the one hand, hte solution is obvious:
cos and exp are decreasing in [0.1], while sin and tan and t*t are increasing strictly, so there always one solution, provided that some certain equation holds.
BUT THIS DOESNT WORK!
it only passses sample inputs successfully, but I got WA still.
Those smart boys who did succeded with this problem, send me your source code, please.
serur@mail.ru