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

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

10096 - The Richest Man of the Universe

Post by Whinii F. » Wed Dec 25, 2002 7:50 am

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
New poster
Posts: 6
Joined: Tue Dec 11, 2001 2:00 am
Location: singapore

Re: 10096: The Richest Man of the Universe.. Can't understan

Post by simon81 » Wed Jan 15, 2003 2:55 pm

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
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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

10096 - Richest Man of the Universe

Post by Per » Tue Jun 10, 2003 11:24 am

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
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

Post by hujialie » Thu Aug 21, 2003 5:56 pm

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
Retired from SJTU Accelerator 2004

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Thu Aug 21, 2003 6:10 pm

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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Thu Dec 11, 2003 10:04 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Dec 12, 2003 12:18 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Dec 12, 2003 12:31 am

Got Accepted again, I forgot one check in my new program. But my old program was surely incorrect, and it gives Accepted :o
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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Fri Dec 12, 2003 7:53 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Mar 10, 2004 11:31 am

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed Mar 10, 2004 11:51 am

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Mar 10, 2004 2:00 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 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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Jul 30, 2004 8:54 pm

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

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Fri Jul 30, 2004 10:12 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Jul 30, 2004 10:35 pm

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.

Post Reply

Return to “Volume 100 (10000-10099)”