## 358 - Don't Have A Cow

Moderator: Board moderators

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
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.

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

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

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

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
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;
}

nahidshahin
New poster
Posts: 8
Joined: Mon Nov 10, 2003 10:54 am
Contact:

### p358 Don't Have A Cow, Dude Why WA

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
nahid

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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

Code: Select all

``````R = 100, P = 0.24, Rope = 75.73
``````
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.
If only I had as much free time as I did in college...

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
You're not getting crazy, but the input in the second case was "6534 0.2355", not "6534 0.24"

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
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;
}
``````

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

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

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

### 358- dont have a cow indeed...

Hi everyone!-
Need some I/O for dont have a cow, dude!

thanx!

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Contact:
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``````
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.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Hi fellows!
Please tell why I'm getting WA.

cut
Last edited by serur on Wed Jun 14, 2006 4:45 pm, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi,

I used EPS to be around 1e-6. Perhaps 1e-12 is too small.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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!
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am