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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Thanks mf. Your inputs are great. I have changed my code. But still WA. .

Code: Select all

``Accepted :)``
Last edited by Jan on Wed Oct 25, 2006 12:36 am, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Try this test case: 0 0 0 0 -1 1.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
My code returns ...

Output:

Code: Select all

``1.0000``
Still found no error....
Ami ekhono shopno dekhi...
HomePage

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
On my computer your program prints 0.0000 for that test.
Last edited by mf on Thu Sep 15, 2005 2:26 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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...
Ami ekhono shopno dekhi...
HomePage

baleezo
New poster
Posts: 2
Joined: Fri Sep 16, 2005 11:35 pm
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

``````
Last edited by baleezo on Mon Sep 19, 2005 5:45 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

baleezo
New poster
Posts: 2
Joined: Fri Sep 16, 2005 11:35 pm
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
New poster
Posts: 2
Joined: Tue Oct 04, 2005 5:46 pm
Contact:

### 10341

//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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Is it just my computer or is your program not even passing the sample input?

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### 10341(solve it)

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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### 10341

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