10096 - The Richest Man of the Universe

[Whinii F.]

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~!

[simon81]

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

The original virus are divided into two small viruses with equal r,
<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.

[Per]

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

[hujialie]

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

[Per]

hujialie: thanks for your reply. My program outputs exactly the same thing as yours (and I havent't been working with this problem since my post, so I'm still WA).

[Caesum]

I am also WA on this. Why in the last case is it not 'not enough space' since the original one will not fit in the box ?

[Adrian Kuegel]

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*w-r*sqrt(8)*(l+w)+r*r*4) (the distance between the circle centers in x direction is l-2*(r/sqrt(2)), and in y direction w - 2*(r/sqrt(2)) ).

[Adrian Kuegel]

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.

[Per]

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.

[little joey]

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?

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.

Thanks in advance.

[Per]

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 M-cases 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).

[little joey]

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 parent-virus 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 epsilon-comparisons 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

Code: Select all

1
S 0 0 0

is

Code: Select all

0.0000

[Per]

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 parent-virus 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.

(sorry, should have replied to this a long time ago)
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.

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.

It all depends on how you define "overlap". I think the usual definition is "having an intersection of non-zero area", i.e. touching is allowed (see the Mathworld page on circle packing).

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?

[little joey]

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.