## 10096 - The Richest Man of the Universe

Moderator: Board moderators

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

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

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 10096 - Richest Man of the Universe

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

New poster
Posts: 7
Joined: Fri Sep 18, 2009 5:15 pm
Location: Dhaka
Contact:

### Re: 10096 - Richest Man of the Universe

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

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

``````

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

### Re: 10096 - Richest Man of the Universe

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
New poster
Posts: 11
Joined: Tue Jul 27, 2010 7:29 pm

### Re: 10096 - Richest Man of the Universe

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10096 - Richest Man of the Universe

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

Code: Select all

``removed, after acc..``
Last edited by lighted on Wed Jul 30, 2014 8:03 pm, edited 3 times in total.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10096 - Richest Man of the Universe

Adrian Kuegel wrote: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?
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10096 - Richest Man of the Universe

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.");
``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10096 - Richest Man of the Universe

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

``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10096 - Richest Man of the Universe

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.
Last edited by lighted on Fri Aug 01, 2014 3:58 am, edited 2 times in total.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10096 - Richest Man of the Universe

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

``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10096 - Richest Man of the Universe

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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10096 - Richest Man of the Universe

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.
Check input and AC output for thousands of problems on uDebug!