10096 - The Richest Man of the Universe

[tobby]

Probably most of the 16 solvers do not read this page any more.

little joey mentioned that he used epsilon comparison? Then what value of epsilon should we use?

[newkid]

reviving this thread again.
Getting lots of WA on this problem. Its frustrating. Can some kind hearted ACer at least post the output for the lovemagic's input.

Thanks

[Azad Salam]

GETTING TOO MANY WA's
My code gives correct answer of all the test cases posted here ..
cant understand where the problem is
Please help

Code: Select all

#include <stdio.h>
#include <math.h>

int main(void)
{
	int n;
	char c;
	double w,l,r,ans,R,d,a1,a2,a,tmp,L,W;
	scanf("%d",&n);
	while(n--)
	{
		scanf(" %c",&c);
		if(c=='S')
		{
			scanf(" %lf %lf %lf",&L,&W,&R);

			
			r= R/1.414213562;

			l = L -2*r;
			w = W -2*r;
			d = sqrt(l*l+w*w);

			if( r+r-d > 0.00000001)
			{
				printf("Not enough space for fission.\n");
			}
			
			else if( 2*r-L >0.00000005 || 2*r-W>0.00000005)
			{
				printf("Not enough space for fission.\n");
			}
			else
			{
				printf("%.4lf\n",d);
			}
			
		}

		else
		{
			scanf(" %lf %lf %lf",&R,&r,&d);
			
			if(R>r)
			{
				tmp =R;
				R=r;
				r=tmp;
			}

			a1 = 3.14159265358 * R * R;
			a2 = 3.14159265358 * r * r;
			
			
			a=r*r * acos(((d*d+r*r-R*R)/(2*d*r))) + R*R * acos(((d*d-r*r+R*R)/(2*d*R))) -  ( sqrt((d + r + R) * (-d + r + R) * (d + r - R) * (d - r + R)) /2 );
			
			if(r+R-d <= 0.00000001)
			{
				printf("1.0000\nNo compaction has occurred.\n");
			}
			else
			{
				ans = a1+a2 -a;
				ans/=(a1+a2);

				if((ans <=1.00005 && ans >= 0.99995))
				{
					printf("1.0000\nNo compaction has occurred.\n");
				}
				else
				{
					printf("%.4lf\n",ans);
				}
			}
		}

		printf("\n");
	}
	return 0;
}

Thanx in advance

[crip121]

for PI use this

Code: Select all

#define PI acos(0.0)

and for floating number comparison use

Code: Select all

fabs(a-b)<=0.000000001

[Zwergesel]

For anyone still struggling with this problem:

I just got AC by changing my code that checks the distance in the fission case to see if there's enough room for both viruses in the box.
distance >= diameter gave WA
distance >= diameter-0.000000001 gave AC

Hope that helps. Good luck!

[lighted]

I got lots of WA. I checked input in this thread. My program ouputs the same output.

Code: Select all

removed, after acc..

[lighted]

Got Accepted again, I forgot one check in my new program. But my old program was surely incorrect, and it gives Accepted
By the way, you should only output "No compaction has occurred." if r1+r2<=d. When I changed my program so that it printed this message in each case where the output is 1.0000, I got WA.

For fusion type of input you have to print the compaction ratio of the virus according to the sample output. Compaction Ratio is defined as (Surface area covered by the merged virus)/(Surface area covered by first virus before merging + Surface Area covered by the second virus before merging). When the printed compaction ration is 1.0000 you will have to print in the next line “No compaction has occurred.” Another important thing is that when no merging has occurred you will have to print the compaction ratio as 1.0000 and in the next line you will have to print, “No compaction has occurred.”

According to problem description we must print in each case where the output is 1.0000. Which one is correct?

[lighted]

Got accepted!
Got more than 50 WAs when eps was 1e-6, 1e-8, 1e-9.
When i changed it to 1e-10 got acc.

We must print "No compaction has occurred." after each case when printed ratio is 1.0000.

Also be careful when checking if ratio is 1.0000. I did it this way.

Code: Select all

sprintf(s, "%.4lf", s2 / s1);  

sscanf(s, "%lf", &r);

printf("%.4lf\n", r);  

if (fabs(r - 1) < eps) puts("No compaction has occurred.");

[lighted]

Input given by lovemagic.

Code: Select all

48 
S 0 0 0 
S 2 2 0 
S 2 0 0 
S 3 0 1 
S 10 10 5 
S 8.48 6 3 
S 8.49 6 3 
S 9 2 1 
S 9 1.999999 1 
S 4 2 1 
S 3.999999 2 1 
S 3.999999 1.999999 1 
S 2000 2000 1 
S 2000 2000 500 
S 10 10 4 
S 4.0 2.0 1.414213562373 
S .1 .1 .025 
S 8.5 8.6267 3.05 
S 8.5 8.62670274 3.05 
S 1 1 .002 
S 4 8 2 
S 4 8 2.0000001 
S 4.00000002 8.00000004 2.00000001 
M 1 2 3 
M 1 2 4 
M 0 0 0 
M 0 0 1 
M 1 0 1 
M .1 .1 .1 
M 1 .00001 1 
M 1 .0001 1 
M 1 .001 1 
M 1 .01 1 
M 1 .1 1 
M 2 3 4.9 
M 2 3 4.99 
M 2 3 4.999 
M 2 3 4.9999 
M 5 3 5 
M 10 10 10 
M 10 9.99 10 
M 5 5.1 10 
M 5 5.01 10 
M 5 5.001 10 
M 5 5 9.888888889 
M 5 5 9.8 
M 5 4.99 9.98 
M 5 4.99 9.97

My acc. program gives same output as output of arif_pasha.

Code: Select all

0.0000

2.8284

2.0000

Not enough space for fission.

Not enough space for fission.

4.5873

4.5966

7.6084

7.6084

2.6513

2.6513

2.6513

2826.4271

1828.4271

6.1421

2.0000

0.0914

6.0111

6.0111

1.4102

5.3026

5.3026

5.3026

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

0.8045

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

0.9952

0.9984

0.9999

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

0.8847

0.8045

0.8046

0.9994

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

0.9993

0.9983

1.0000
No compaction has occurred.

0.9999

[lighted]

This test gave me Zwergesel.

Code: Select all

9
S 0 0.00015 0
S 0 0.00025 0
S 0 0.00055 0
S 0 0.00065 0
S 0 0.00075 0
S 0 0.00085 0
S 0.00063 0.00016 0
S 0.00072 0.00021 0
S 0.001 0.00075 0

Acc. output of Zwergesel.

Code: Select all

0.0002

0.0002

0.0005

0.0007

0.0007

0.0009

0.0007

0.0007

0.0012

My acc. program gives

Code: Select all

0.0001

0.0003

0.0006

0.0006

0.0008

0.0008

0.0006

0.0008

0.0013

By the way Zwergesel got accepted with eps 1-8 or 1-9.
So i think eps value depends on calculation way that you make.

[lighted]

Per's input

Code: Select all

16
S 10 10 4.5
M 5 5 9.98
M 5 5 9.99
M 5 0.05005 5
M 5 0.05006 5
M 1999 1999 1999
M 2000 2000 2000
M 1000 1500 2000
S 0.0 0 0.0
S 0.00005001 0.0 0.0
S 1 1 0.00
S 1 1 0.01
S 0.02 0.02 0.0082842
S 0.02 0.02 0.0082843
S 0.02 0.02 0.0082844
S 4.0 2.0 1.414213562373

My acc. program gives

Code: Select all

Not enough space for fission. 

0.9999 

1.0000 
No compaction has occurred. 

1.0000 
No compaction has occurred. 

0.9999 

0.8045 

0.8045 

0.9513 

0.0000 

0.0001 

1.4142 

1.3942 

0.0117 

Not enough space for fission. 

Not enough space for fission. 

2.0000

[lighted]

little joey's input

Code: Select all

12
M 10 4 15
M 10 4 14
M 10 4 13.99999
M 10 4 13
M 10 4 10
S 20 10 0
S 20 10 4.99999
S 20 10 5
S 20 10 5.00001
S 20 10 7.07
S 20 10 7.08
S 20 10 100

My acc. program gives

Code: Select all

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

0.9914

0.9369

22.3607

13.2566

13.2565

13.2565

10.0015

Not enough space for fission.

Not enough space for fission.

I hope that all people who can't get accepted will get it.

[brianfry713]

In order to get AC: for fission, don't check if the initial virus can fit in the box but check if the two new virus's can fit.