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:

Post by mf » Wed Sep 14, 2005 5:31 am

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Sep 14, 2005 6:35 am

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:

Post by mf » Wed Sep 14, 2005 8:31 am

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Sep 14, 2005 8:52 am

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:

Post by mf » Wed Sep 14, 2005 9:55 am

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Sep 14, 2005 6:16 pm

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:

Post by mf » Wed Sep 14, 2005 11:47 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Sep 15, 2005 10:41 am

Thanks mf :D .
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... :wink:
Ami ekhono shopno dekhi...
HomePage

baleezo
New poster
Posts: 2
Joined: Fri Sep 16, 2005 11:35 pm

Post by baleezo » Fri Sep 16, 2005 11:42 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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Sep 17, 2005 11:12 pm

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.
Ami ekhono shopno dekhi...
HomePage

baleezo
New poster
Posts: 2
Joined: Fri Sep 16, 2005 11:35 pm

Post by baleezo » Sun Sep 18, 2005 7:38 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

Post by vardiar » Tue Oct 04, 2005 5:53 pm

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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Tue Dec 27, 2005 3:43 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)

Post by serur » Thu Feb 23, 2006 11:38 pm

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

Post by serur » Thu Feb 23, 2006 11:48 pm

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

Post Reply

Return to “Volume 103 (10300-10399)”