358 - Don't Have A Cow

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post 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

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

Post 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

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

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

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

p358 Don't Have A Cow, Dude Why WA

Post 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
nahid

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post 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

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

Post by little joey »

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

Post 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 :P

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

Post by Antonio Ocampo »

Please help me, I'm stuck in this problem :cry:

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

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

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

358- dont have a cow indeed...

Post by serur »

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

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

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

Post by serur »

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
Location: TORONTO, CANADA

Post by daveon »

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

Post 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!
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
Location: TORONTO, CANADA

Post 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. :wink:

Post Reply

Return to “Volume 3 (300-399)”