358 - Don't Have A Cow

[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

[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

[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;
}

[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

[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

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.

[little joey]

You're not getting crazy, but the input in the second case was "6534 0.2355", not "6534 0.24"

[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

[Antonio Ocampo]

Please help me, I'm stuck in this problem

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

[serur]

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


thanx!

[arif_pasha]

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.

[serur]

Hi fellows!
Please tell why I'm getting WA.

cut

[daveon]

Hi,

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

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

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