10096  The Richest Man of the Universe
Moderator: Board moderators

 Experienced poster
 Posts: 151
 Joined: Wed Aug 21, 2002 12:07 am
 Location: Seoul, Korea
 Contact:
10096  The Richest Man of the Universe
Hi,
I'm trying to solve the problem 10096. And can't understand the mechanism how "fission" works. At first I thought there will be two viruses equally sized R.
Then the sample input doesn't make sense. If the two viruses stick to corners opposing each other, then the distance will be:
sqrt(sqr(9.1)+sqr(9.1)) = 12.8693
Next I thought that the two viruses are evolving from the initial one, so sum of the two viruses' areas should be equal to that of the initial one. But that way gives 13.2836 .. Which is precisely 1 larger than the sample output.
What am I doing wrong? Am I missing something in the problem statement? I read it several times but am still confused.
Plz Help~!
I'm trying to solve the problem 10096. And can't understand the mechanism how "fission" works. At first I thought there will be two viruses equally sized R.
Then the sample input doesn't make sense. If the two viruses stick to corners opposing each other, then the distance will be:
sqrt(sqr(9.1)+sqr(9.1)) = 12.8693
Next I thought that the two viruses are evolving from the initial one, so sum of the two viruses' areas should be equal to that of the initial one. But that way gives 13.2836 .. Which is precisely 1 larger than the sample output.
What am I doing wrong? Am I missing something in the problem statement? I read it several times but am still confused.
Plz Help~!
Re: 10096: The Richest Man of the Universe.. Can't understan
The original virus are divided into two small viruses with equal r,Whinii F. wrote:
Then the sample input doesn't make sense. If the two viruses stick to corners opposing each other, then the distance will be:
sqrt(sqr(9.1)+sqr(9.1)) = 12.8693
<h>without loss of total area<h>
so after fussion, r = sqrt(2)*0.5*R;
then when you calcuate distance of the two viruses, the sample input
does make sense.
But I still get W.A for this problem.
Maybe the bug lies in the precession of output.
10096  Richest Man of the Universe
This problem is giving me lots of trouble. Could someone give me the output for the following 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
To Per:
My programme got output from your input as follows,but it is also wrong answer.
Is your output the same?
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
My programme got output from your input as follows,but it is also wrong answer.
Is your output the same?
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
Retired from SJTU Accelerator 2004

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Hi,
I got this problem Accepted some time ago. Now I looked again at my code and now I think the formula I used is wrong. I just checked, my old program gives still Accepted, while my new program that I have written now (and which I think is correct) got WA.
The mistake is in the fission part of the problem. Of course the two circles have to be in opponent corners to get a maximum distance
It is easy to calculate that the distance from a circle center of the two smaller circles to the corner is equal to the radius of big circle.
In my program that got Accepted I calculated the distance then as sqrt(l*l+w*w)2*r, which is of course wrong, because the circle centers don't have to be on the line connecting the two opposite corners.
The right formula should be sqrt(l*l+w*wr*sqrt(8)*(l+w)+r*r*4) (the distance between the circle centers in x direction is l2*(r/sqrt(2)), and in y direction w  2*(r/sqrt(2)) ).
I got this problem Accepted some time ago. Now I looked again at my code and now I think the formula I used is wrong. I just checked, my old program gives still Accepted, while my new program that I have written now (and which I think is correct) got WA.
The mistake is in the fission part of the problem. Of course the two circles have to be in opponent corners to get a maximum distance
It is easy to calculate that the distance from a circle center of the two smaller circles to the corner is equal to the radius of big circle.
In my program that got Accepted I calculated the distance then as sqrt(l*l+w*w)2*r, which is of course wrong, because the circle centers don't have to be on the line connecting the two opposite corners.
The right formula should be sqrt(l*l+w*wr*sqrt(8)*(l+w)+r*r*4) (the distance between the circle centers in x direction is l2*(r/sqrt(2)), and in y direction w  2*(r/sqrt(2)) ).

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
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.
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.
Thanks Adrian,
my problem was that I printed "No compaction..." when the printed output was 1.0000, as the problem says. I think either the problem statement should be changed or the problem rejudged.
I used the same formula as your correct formula (though it took me a few seconds to recognise it). It's strange that the incorrect formula gets AC as well, I guess judge's input only contains cases where w=l.
my problem was that I printed "No compaction..." when the printed output was 1.0000, as the problem says. I think either the problem statement should be changed or the problem rejudged.
I used the same formula as your correct formula (though it took me a few seconds to recognise it). It's strange that the incorrect formula gets AC as well, I guess judge's input only contains cases where w=l.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Per:
After trying to understand Shahriar's description, coding, many WAs, reading this forum, patching the code, more WAs, discovering you made a new testset, recoding and even more WAs, can I ask you in which way your testset responds to the above mentioned 'anomalities'?
Or, more specificaly, is the following i/o correct?
Thanks in advance.
After trying to understand Shahriar's description, coding, many WAs, reading this forum, patching the code, more WAs, discovering you made a new testset, recoding and even more WAs, can I ask you in which way your testset responds to the above mentioned 'anomalities'?
Or, more specificaly, is the following i/o correct?
Code: Select all
16
M 10 4 15
M 10 4 14
M 10 4 13.99999
M 10 4 13
M 10 4 10
M 10 4 9
M 10 4 6
M 10 4 5
M 10 4 0
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
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
0.9151
0.8621
0.8621
0.8621
22.3607
13.2566
13.2565
Not enough space for fission.
Not enough space for fission.
Not enough space for fission.
Not enough space for fission.
The two first "Not enough space for fission" are incorrect. They should be 13.2565 and 10.0015. Otherwise, the output is correct.
Some small things: the last four Mcases are invalid, since the statement guarantees d >= max(R1, R2) (my program answers the same as yours for these cases). Also, there should be a blank line after the output of the last test case (perhaps you just didn't include it in your post, but I'll remind you anyway).
Some small things: the last four Mcases are invalid, since the statement guarantees d >= max(R1, R2) (my program answers the same as yours for these cases). Also, there should be a blank line after the output of the last test case (perhaps you just didn't include it in your post, but I'll remind you anyway).

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Thanks, got AC now.
I'm not conviced of the fact that the first two "Not enough..."s should be replaced by numbers, because, as Caesum correctly remarked, there is not enough room in the box to hold the parentvirus in the first place. Which means that there is not enough room for the fission, which means that the answer should be "Not enough...", according to the problem description. But I don't know if there are such cases in the input.
I printed the extra blank line, but had to change my comparisons to epsiloncomparisons to get accepted.
Thanks again.
I'm not conviced of the fact that the first two "Not enough..."s should be replaced by numbers, because, as Caesum correctly remarked, there is not enough room in the box to hold the parentvirus in the first place. Which means that there is not enough room for the fission, which means that the answer should be "Not enough...", according to the problem description. But I don't know if there are such cases in the input.
I printed the extra blank line, but had to change my comparisons to epsiloncomparisons to get accepted.
Thanks again.
Thanks for all the people involved in the thread, I get accepted after about 20 WA.
The problem says "Fission is impossible if the viruses cannot remain separated (not overlapped) in the box at any possible position."
At first, I think if the distance between virus is zero, I should consider it as impossible. However, it seems that the judge input only use the rule "distance < 2*radius" to decide if it is possible. That is, the output of
is
The problem says "Fission is impossible if the viruses cannot remain separated (not overlapped) in the box at any possible position."
At first, I think if the distance between virus is zero, I should consider it as impossible. However, it seems that the judge input only use the rule "distance < 2*radius" to decide if it is possible. That is, the output of
Code: Select all
1
S 0 0 0
Code: Select all
0.0000
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.
(sorry, should have replied to this a long time ago)little joey wrote:I'm not conviced of the fact that the first two "Not enough..."s should be replaced by numbers, because, as Caesum correctly remarked, there is not enough room in the box to hold the parentvirus in the first place. Which means that there is not enough room for the fission, which means that the answer should be "Not enough...", according to the problem description. But I don't know if there are such cases in the input.
Actually, to be picky, the problem statement only says "Fission is impossible if the viruses cannot remain separated (not overlapped) in the box at any possible position." That is, it doesn't say anything about fission being impossible because the original virus doesn't fit. (I admit that this argument is a bit silly). But I guess it wouldn't hurt if this was made clearer.
It all depends on how you define "overlap". I think the usual definition is "having an intersection of nonzero area", i.e. touching is allowed (see the Mathworld page on circle packing)... wrote:The problem says "Fission is impossible if the viruses cannot remain separated (not overlapped) in the box at any possible position."
At first, I think if the distance between virus is zero, I should consider it as impossible. However, it seems that the judge input only use the rule "distance < 2*radius" to decide if it is possible.
I could ask Carlos to add some sample cases to clarify these two points, but I don't think it's worth changing the judge I/O again. What do you think?

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm