10341 - Solve It

[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

[Jan]

Thanks mf. Your inputs are great. I have changed my code. But still WA. .

Code: Select all

Accepted :)

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

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

[mf]

Try this test case: 0 0 0 0 -1 1.

[Jan]

My code returns ...

Output:

Code: Select all

1.0000

Still found no error....

[mf]

On my computer your program prints 0.0000 for that test.

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

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

Code: Select all

Accepted

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

[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

Code: Select all

Accepted :)

[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]

[daveon]

Is it just my computer or is your program not even passing the sample input?

[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?

[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