Page 3 of 4
Posted: Tue Feb 10, 2004 7:38 am
by junbin
I'm trying to solve q358 Don't Have A Cow, Dude and I keep getting WA, though my answers correspond to all the test data I can find...
I've tried 4 different methods:
1) Estimating rope length using binary search
2) Estimating angle between radii of both circles using binary search
2) Estimating angle between radii of both circles using Newton Raphson
3) Estimating rope length using binary search (another formulation)
All 4 methods give me the WA.
If possible, can someone please answer my queries:
1) What are the parameters for floating point? I use:
long double
epsilon = 1e-6
pi = 3.14159
2) Is p supposed to be printed to 2 dp or do I print it as it is given in the input?
3) When I print the rope length to 2 dp, can I simply use:
printf("%.2llf", rope);
or do I have to use a special formatting function?
ie: round up at >= 0.005
If possible, can someone please verify my test data?
test data:
Code: Select all
15
50 0.0
100 0.2
1000 0.25
1000 0.50
999 0.49
958 0.24
434 0.12
4546 0.23545
6534 0.2355
54654 0.2356
934959 0.25656
459876 0.4377834
213 0.111
456 0.23
34 0.1
my output:
Code: Select all
R = 50, P = 0.00, Rope = 0.00
R = 100, P = 0.20, Rope = 68.48
R = 1000, P = 0.25, Rope = 774.75
R = 1000, P = 0.50, Rope = 1158.73
R = 999, P = 0.49, Rope = 1143.33
R = 958, P = 0.24, Rope = 725.53
R = 434, P = 0.12, Rope = 225.50
R = 4546, P = 0.24, Rope = 3406.47
R = 6534, P = 0.24, Rope = 4896.73
R = 54654, P = 0.24, Rope = 40968.59
R = 934959, P = 0.26, Rope = 734915.30
R = 459876, P = 0.44, Rope = 491686.08
R = 213, P = 0.11, Rope = 106.17
R = 456, P = 0.23, Rope = 337.29
R = 34, P = 0.10, Rope = 16.03
Posted: Tue Feb 10, 2004 1:32 pm
by sjn
Code: Select all
R = 6534, P = 0.24, Rope = 4896.72
R = 54654, P = 0.24, Rope = 45239.76
R = 934959, P = 0.26, Rope = 787659.93
R = 459876, P = 0.44, Rope = 565385.06
hope helpful
Posted: Thu Feb 12, 2004 5:47 pm
by junbin
I'm using the following four functions to evaluate the length of rope... but all four give me WA. Anyone knows which function will get AC?
// Binary search for angle between the two radii
// invpi = (1 - p) * pi
ft calculate(ft x, ft invpi) {
ft cosx;
cosx = cos(x);
return (4 * x * cosx * cosx) + invpi - (2 * x) - (2 * cos(x) * sin(x));
}
// Newton Raphson Search (nu = f(x), de = f'(x)) for angle between radii
ft caloff(ft x, ft p) {
ft nu, de;
nu = (4 * x * cos(x) * cos(x)) + ((1 - p) * pi) - (2 * x) - sin(2 * x);
de = (4 * cos(x) * cos(x)) - (8 * x * cos(x) * sin(x)) - 2 - (2 * cos( 2 * x ));
return nu / de;
}
// Binary search for the rope length
ft calculate2(ft R, ft r, ft p) {
ft x = acos(((2 * r * r) - (R * R)) / (2 * r * r));
ft area = ((x - sin(x)) * r * r) + ((pi - x) * R * R * 0.5);
ft needarea = pi * r * r * p;
return area - needarea;
}
// Binary search for the ratio of the "eatable" area and the total area of field
ft calculate3(ft R, ft r, ft area) {
ft x = acos(((2 * r * r) - (R * R)) / (2 * r * r));
ft narea = ((x - sin(x)) * r * r) + ((pi - x) * R * R * 0.5);
return narea / area;
}
p358 Don't Have A Cow, Dude Why WA
Posted: Wed Sep 15, 2004 5:28 am
by nahidshahin
I don't understand why I get wa in this easy problem.
The idea is easy. (Bsearch)
But what is the reson of wa.
Can any one give any correction ?
Here My code
Code: Select all
#include <stdio.h>
#include <math.h>
#define esp 0.000001
double pi,r,p;
double area(double rp) {
double x,y,theta,arp,ar;
x = (rp*rp)/(2.0*r);
y = sqrt((rp*rp) - (x*x));
theta = pi - (2.0*asin(x/rp));
arp = ((theta*rp*rp)/2.0) - (x*y);
theta = pi - (2.0*asin(fabs(r-x)/r));
ar = ((theta*r*r)/2.0) - (fabs(r-x)*y);
return arp+ar;
}
int main() {
int cn,st=1;
double l,h,m,trg,a;
#ifndef ONLINE_JUDGE
freopen("inp.txt","r",stdin);
#endif
pi = 2.0*acos(0);
scanf("%d",&cn);
while(cn--) {
if(st == 1)
st = 0;
else
printf("\n");
scanf("%lf%lf",&r,&p);
if(fabs(p) < esp) {
printf("R = %d, P = %.2lf, Rope = %.2lf\n",(int)r,p,0.0);
continue;
}
l = 0.0;
h = 2.0*r;
trg = r*r*pi*p;
while(l<(h+esp)) {
m = (l+h)/2.0;
a = area(m);
if(fabs(a - trg) < esp)
break;
else if(a < trg)
l = m+esp;
else
h = m-esp;
}
printf("R = %d, P = %.2lf, Rope = %.2lf\n",(int)r,p,m);
}
return 0;
}
Thanks
Posted: Sun Jul 24, 2005 5:25 am
by Abednego
Am I crazy, or is the value of Rope linear in R? If it is, then, sjn, how can you possibly have these answers? First you say
And then
Code: Select all
R = 6534, P = 0.24, Rope = 4896.72
But the value of P is the same, so 75.73/100 = 4896.72/6534, which is not true.
I get the same answers as your big input/output (thanks for posting it), but it's WA.
Posted: Sun Jul 24, 2005 10:54 am
by little joey
You're not getting crazy, but the input in the second case was "6534 0.2355", not "6534 0.24"
Posted: Wed Nov 09, 2005 1:32 am
by Antonio Ocampo
Hi folks. Could someone give me any critical I/O? I got several WA in this problem I guess is a precision error.
Btw, this is my code(i'm using Newton-Raphson Method)
Code: Select all
#include <stdio.h>
#include <math.h>
int main()
{
int r,casos;
double error,p0,p1,eps=1e-6,f,df,k,p,pi=3.14159;
scanf("%i",&casos);
do
{
scanf("%i%lf",&r,&p);
if(p>eps)
{
k=pi*(1-p);
p0=0.9*pi;
f=p0*cos(p0)-sin(p0)+k;
do
{
df=-p0*sin(p0);
p1=p0-f/df;
error=fabs(p1-p0);
p0=p1;
f=p0*cos(p0)-sin(p0)+k;
}
while( error>eps && fabs(f)>eps );
if(casos!=1)
printf("R = %i, P = %.2lf, Rope = %.2lf\n\n",r,p,2*r*cos(0.5*p0));
else
printf("R = %i, P = %.2lf, Rope = %.2lf\n",r,p,2*r*cos(0.5*p0));
}
else
{
if(casos!=1)
printf("R = %i, P = 0.00, Rope = 0.00\n\n",r);
else
printf("R = %i, P = 0.00, Rope = 0.00\n",r);
}
}
while(--casos);
return 0;
}
Thx in advance
Posted: Wed Nov 16, 2005 6:05 am
by Antonio Ocampo
Please help me, I'm stuck in this problem
Posted: Fri Dec 23, 2005 1:19 am
by daveon
Hi,
You may try using BI-SECTION method with the formula from mathworld.
Just search for "goat problem" on mathworld.
I got many WAs before I used this formula.
358- dont have a cow indeed...
Posted: Tue Mar 28, 2006 9:17 pm
by serur
Hi everyone!-
Need some I/O for dont have a cow, dude!
thanx!
Posted: Wed May 10, 2006 8:39 pm
by arif_pasha
sjn wrote:Code: Select all
R = 6534, P = 0.24, Rope = 4896.72
R = 54654, P = 0.24, Rope = 45239.76
R = 934959, P = 0.26, Rope = 787659.93
R = 459876, P = 0.44, Rope = 565385.06
hope helpful
my acc code give different result than
sjn. for
junbin's input my output is following..
Code: Select all
R = 50, P = 0.00, Rope = 0.00
R = 100, P = 0.20, Rope = 68.48
R = 1000, P = 0.25, Rope = 774.75
R = 1000, P = 0.50, Rope = 1158.73
R = 999, P = 0.49, Rope = 1143.33
R = 958, P = 0.24, Rope = 725.53
R = 434, P = 0.12, Rope = 225.50
R = 4546, P = 0.24, Rope = 3406.47
R = 6534, P = 0.24, Rope = 4896.72
R = 54654, P = 0.24, Rope = 40968.50
R = 934959, P = 0.26, Rope = 734913.95
R = 459876, P = 0.44, Rope = 491685.51
R = 213, P = 0.11, Rope = 106.17
R = 456, P = 0.23, Rope = 337.29
R = 34, P = 0.10, Rope = 16.03
btw: i used bin search + simple trig & geo to solve this problem.
Posted: Wed Jun 07, 2006 4:42 pm
by serur
Hi fellows!
Please tell why I'm getting WA.
cut
Posted: Fri Jun 09, 2006 5:16 am
by daveon
Hi,
I used EPS to be around 1e-6. Perhaps 1e-12 is too small.
Posted: Wed Jun 14, 2006 4:46 pm
by serur
Hi fellows!
Please, look and tell me what's the difference between your AC code and this stuff (which gives WA)?
Code: Select all
#include <stdio.h>
#include <math.h>
#define eps 1e-6
#define Pi 3.14159
#define pi 2 * acos(0.0)
const char *format = "R = %d, P = %.2lf, Rope = %.2lf\n";
double target_area;
double area(double x)
{
double Cos = cos(x);
return(x * Cos - sin(x) + pi * (1 - Cos));
}
double get_root(int R, double P)
{
double u, v, c;
for(u = 0.0, v = pi; v - u > eps;)
{
c = (u + v) / 2;
(area(c) < target_area) ? (u = c) : (v = c);
}
return u;
}
int main()
{
int R;
double P;
int cs;
#ifndef ONLINE_JUDGE
freopen("358.in","r",stdin);
#endif
for(scanf("%d\n",&cs);cs -- ;){
scanf("%d %lf\n", &R, &P);
target_area = Pi * P;
printf(format,R,P,2 * R * sin(get_root(R,P) / 2));
}
return 0;
}
Thank you!
Posted: Thu Jun 15, 2006 4:29 am
by daveon
Hi,
The formula I used was a lot more complicated and can be found on Mathworld. Just look for "Goat problem".
Hope you get accepted.
