10096 - The Richest Man of the Universe

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

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
little joey wrote:No, I see no point in changing the I/O again. There's enough information in this forum for everybody to succesfully solve this problem, I think, so a clarification is probably not necessary. But maybe the problemsetter should decide, if he still reads the boards.
I agree with little joey, the infromation in this thread should be enough to solve the problem.

Actually I think this problem is not well defined when some input value is zero, but you know, Shahriar Manzoor always likes to play this trick... My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

10096

i don't know why my 10096 gets WA after rejudging!
my code gives these output for the inputs.
plz tell me are these right or wrong && if wrong what's the right?

input

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

output

0.0000

2.8284

2.0000

Not enough space for fission.

Not enough space for fission.

Not enough space for fission.

4.3962

7.2195

Not enough space for fission.

2.4721

2.4721

Not enough space for fission.

2826.4271

1828.4271

Not enough space for fission.

Not enough space for fission.

0.0914

Not enough space for fission.

6.0107

1.4102

4.9443

Not enough space for fission.

4.9443

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
khobaib

Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:

10096 fission?

Can somebody explain me the process of fission in 10096? Does the initial virus (with the specs got from the input) splits in two viruses with radii equal one half the initial or we have to split up two viruses of input sizes?

New poster
Posts: 4
Joined: Sat Oct 23, 2004 11:53 am
Location: Czech Republic
Contact:
Good morning,

I tried to solve the problem and heeded the hints, you talked about on this forum, but it still gives me WA. In fission I'm using sqrt((l-r*sqrt(2))^2 + (w-r*sqrt(2)^2), which is hopefully right, and in fussion I add surface area covered by first circle to the surface area covered by second circle and then subtract the overlapped area.

The result of this is that it gives me the exactly same output as it gives to you on this forum, but the judge still keeps giving me WA as answer. I tried to print "No compaction occured" only when r1+r2<=d, but it didn't work, so I change my program to print it everytime I get 1.0000, but it didn't work either.

I really don't know, what to do now. Can you help me, please?

Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:
No need to bother. I figured it out. r2=r1/sqrt(2)

New poster
Posts: 4
Joined: Sat Oct 23, 2004 11:53 am
Location: Czech Republic
Contact:

10096 Richest Man of the Universe - Fussion

Can somebody tell me, please, how the fussion part of the Richest Man of the Universe problem (i.e. 10096) has to be calculated? I tried to solve the problem, but I still get WA. In fission I'm using sqrt((l-r*sqrt(2))^2 + (w-r*sqrt(2))^2), which is hopefully right. In fussion I'm using the following code:

[c] r1sqr = sqr(r1);
r2sqr = sqr(r2);
dsqr = sqr(d);
alpha = acos( (r1sqr + dsqr - r2sqr) / (2 * r1 * d) );
beta = acos( (r2sqr + dsqr - r1sqr) / (2 * r2 * d) );
surface1 = PI * r1sqr;
surface2 = PI * r2sqr;
surfaceU1 = (r1sqr / 2) * (2 * alpha - sin(2 * alpha));
surfaceU2 = (r2sqr / 2) * (2 * beta - sin(2 * beta));
surfaceBeforeFussion = surface1 + surface2;
surfaceAfterFussion = surface1 + surface2 - surfaceU1 - surfaceU2;
return (surfaceAfterFussion / surfaceBeforeFussion);
[/c]

thus, I add surface area of the first circle to the surface area of the second circle and then subtract their overlapped area, which I compute from circle segments of each circle.
I think, that in some situations this code isn't giving right results (either by rounding or for some other mystical reasons), but I don't know how to substitute it. Could you, please, help me with this? I would be most grateful.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Have you searched the forum before posting??
http://online-judge.uva.es/board/viewto ... ight=10096
My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

New poster
Posts: 4
Joined: Sat Oct 23, 2004 11:53 am
Location: Czech Republic
Contact:
Yes, I have... And I have also posted a message there. My program gives the same results as the programs there and I have tried to add/remove different conditions to get Accepted, but still, it isn't working. But there's not a word about fussion in the thread you posted me. And I think that fussion is the wrong part in my program. I think that there is a rounding error after all those arccosines and multiplies and divisions. I think that there is some other way to calculate it, but I can't find it. Could you possibly help me with that?

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:
i got the following for your input.. but still wa. can AC ones post their output for those test case?

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

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:
Hi, i am also gettin a lots of wa's

can anyone answer my following questions

1.>
what do you print in fusion part, if the ratio is 0.99995...?
0.9999
or
1.0000
or
1.0000
No compaction occured.

2.>
[fission] let the radius of two new circles are "r". I "printed not enough space" if either L<2r or W<2r or distance d<2r. is it correct?

nukeu666
New poster
Posts: 44
Joined: Sun Feb 13, 2005 1:13 am
Location: India
Contact:
could any of the people who got accepted please help out with this problem
ive tried all the inputs on these forums and guess im getting them right

dipaly
New poster
Posts: 20
Joined: Tue Sep 19, 2006 6:18 pm
Contact:

10096(10 WA):-( help plz

hi everyone. I get 10 WA in 10096.

I have some qns.
if there is any special case for fission & fussion?

for fussion if d==r1+r2; .. what should be the output?
if 0(zero) can be a input?from prev.. post i saw that the output for this input
S 0.0 0.0 0.0 is 0.0000----> is it correct?

in fission if the initial virus's radious R >(l,w) then what should i do:

for fission i do following work in my code

Code: Select all

void fission(double l, double w, double R)
{
if(w>l)
{
double t=l;
l=w;
w=t;
}
if(R > 0 && R<=l && R<=w)
{
double r = R/sqrt(2);
if((l>=4*r) && (w>=2*r))
{
double a = l-2*r , b = w-2*r;
double c = sqrt(a*a + b*b);
printf("%.4lf\n",c);
}
else
printf("Not enough space for fission.\n");
}
else if(R==0&&w==0&&l==0)
{
double g=0;
printf("%.4lf\n",g);
}
else
printf("Not enough space for fission.\n");
}

[/b]for fussion i do following job..
void len(double r, double R, double d)
{
if(d >= (r+R))
{
printf("1.0000\nNo compaction has occured.\n");

}

else
{
if(r !=0 && R !=0 && d != 0)
{
double a1 = (d*d) + (r*r) - (R*R) ,a2 = d*d+R*R-r*r,a3=2*d*r,a4=2*d*R;
double b1 = a1/a3, b2 = a2/a4 ,b3 = -d+r+R ,b4=d+r-R,b5=d-r+R,b6=d+r+R;
double c1 = r*r*acos(b1),c2=R*R*acos(b2),c3=b3*b4*b5*b6;
double c4 = (sqrt(c3))/2;
double z = c1+c2-c4;
double com = (M_PI*r*r +M_PI*R*R -z) / (M_PI*r*r+M_PI*R*R);
if(com==1.0000)
printf("1.0000\nNo compaction has occurred.\n");
else
printf("%.4lf\n",com);
}
else
printf("1.0000\nNo compaction has occurred.\n");
}
}

plz help me   everything is so hard to me

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:
After a lot of tries and of course a lot of WA's i decided to give up this problem..   Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
This problem shouldn't be that hard, should it? I tried it about a year ago and gave up back then. I just tried it again and I can't get an AC.

I was about to recode it in C and see if it helped, but then decided against it. It's not worth it. I might try it when it becomes one of the last unsolved problems for me. "Might" being the key word.

Can someone explain to me what zeros would mean as any part of the input? Zero radius virus? Or a zero length box? It is obvious they are there, because of the wording. I guess we should deal with corner cases, but this is just introducing nonsense to make a problem "harder". I don't get it. And, I am guessing here, I have to use the exact order of operations that the problemsetter used or something. And the same rounding. I am using acos(), maybe he used asin() or something... Blah.

I guess 16 people solved it, so I shouldn't complain. 16 people. Come on...

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Hello, men!
I tried to solve this one myself with no help, then I read the thread - result is the same - WA. I have now decided to write here for help... Watch my code please and say, where am I wrong, if my input is the same as little joey's on the previous page (except wrong composed cases with 'M').

Thank you all in advance:

Code: Select all

program Project3;

{\$APPTYPE CONSOLE}

uses
SysUtils, Math;

var
r1,r2,be,ce,alpha,beta,s,ae,d,l,w,ans,r,l1,l2: extended;
c: char;
ci,cn: integer;

begin

for ci := 0 to cn - 1 do
begin
if ci>0 then
writeln;

if c='M' then
begin

if r1+r2 <= d then
begin
writeln ('1.0000');
writeln ('No compaction has occurred.');
continue
end;

if d<=abs(r1-r2) then
s := min (pi*r1*r1,pi*r2*r2)
else
begin
ae := (r1*r1 - r2*r2 + d*d)/(2*d);
be := d - ae;
ce := sqrt (r1*r1 - ae*ae);
alpha := 2*arctan (ce/ae);
if alpha<0 then
alpha := alpha + pi;
beta := 2*arctan (ce/be);
if beta<0 then
beta := beta + pi;
s := (r1*r1*(alpha-sin(alpha)) + r2*r2*(beta-sin(beta)))/2.0
end;
ans := (pi*r1*r1 + pi*r2*r2);
ans := (ans - s) / ans;

writeln (ans:0:4);

if abs(ans-1)<1e-5 then
writeln ('No compaction has occurred.');

end
else
begin

d := sqrt(l*l+w*w-r*sqrt(8)*(l+w)+r*r*4);

if (r<>0) and ((sqrt(w*w+l*l) - d < 1e-5) or (l-sqrt(2)*r < 1e-5) or (w-sqrt(2)*r < 1e-5)) then
begin
writeln ('Not enough space for fission.');
continue
end;

ans := d;

writeln (ans:0:4);

end;

end;

writeln

end.
Now I lay me down to sleep...
my profile