Page **1** of **2**

### 10648 - Chocolate Box

Posted: **Tue May 04, 2004 10:48 pm**

by **Virtual GOD**

Hi!

Can anybody explain me task 10648 (Chocolate Box)? I don't understand it while contest and now... For example, what means "n types of chocolate"? It is that we have N different chocolates? and what means "What is the probability that one or more boxes are empty?"... one or more??

Thanks

Posted: **Tue May 04, 2004 11:14 pm**

by **Adrian Kuegel**

n types of chocolate means, you have n chocolate pieces, but all look different, so you can distinguish them.

And you have to calculate the probability that at least one box is empty. So this is exactly 1 - probability that all boxes have at least one piece of chocolate in it.

### 10648 - Chocolate Box

Posted: **Fri May 07, 2004 12:49 pm**

by **rotoZOOM**

Hello !

I've found that for calculation probabelities that all boxes are filled I have to deal with Biiiiiiiiiiiig numbers. How I calculate:

For example, let's take 5 types of chocolates and 3 boxes.

All possible distinguished variants for placement chocolates is:

Box1 Box2 Box3

I I III

I II II

Let's take first placemets. All possible variants of box permutation is 3!/2! (as two boxes will have equally number of chocolates). Probabilities such one placement would be 1/(3^5). Permutation of chocolates themselves inside boxes will be 5!/3! (as one of boxes will have 3 chocolates). Well, common probabilities placement of first type is 1/(3^5)*(3!/2!)*(5!/3!)=60/243

Calculate probabilities for second type placement like for first one.

All possible variants of box permutation is 3!/2!. Probabilities such one placement would be 1/(3^5). Permutation of chocolates themselves inside boxes will be 5!/(2!*2!). Well, common probabilities placement of second type is 1/(3^5)*(3!/2!)*(5!/(2!*2!))=90/243

Common probabilities for all placement where all boxes are filled:

60/243+90/243=150/243

So probabilities at least one boxes is empty is (1-150/243).

I show easy example. But when quantity of chocolates and boxes grows, numbers become too large.

Should I use long ariphmetic ?

Posted: **Fri May 07, 2004 1:02 pm**

by **UFP2161**

I used "long double" which was enough precision to get an answer. Normal "double" may work as well.

### distinguishability of choclates

Posted: **Fri May 14, 2004 12:35 pm**

by **abishek**

I would like to know how the fact that the choclates are distinguishable affect the answer.

The probabilty that we put a choclate into any of the boxes is same, and so distinguishable or not the probability is the same.

I used a markov chain to model this event and found P^n for the one step transition matrix

where the state is number of filled boxes

but the answer goes to 1 or 0 only in the matrix.

help

abi

Posted: **Fri May 14, 2004 2:50 pm**

by **UFP2161**

If you had 2 chocolates and 2 boxes:

If they were distinguishable (label them A and B), the unique ways to box them are:

[AB] []

[] [AB]

[A]

** [A]**

Thus, the probability that at least one is empty is 1/2.

However, if they were not distnguishable, you would have:

[AA] []

[] [AA]

[A] [A]

Thus, the probability that at least one is empty is 2/3.

Posted: **Thu May 27, 2004 8:16 pm**

by **Alexander Kozlov**

Please, can sombody give an example of input and correct output for this problem?

Thanks in advance!

Posted: **Fri Jun 11, 2004 11:05 pm**

by **shuniu**

I used double in my Java program, got WA, I wonder if there is precision error. Here are some of my IO, please tell me if there are errors.

Input:

Code: Select all

```
100 0
100 5
100 6
100 7
100 10
100 20
100 30
100 40
100 50
100 59
100 60
100 61
100 70
100 80
100 90
100 100
-1
```

Output:

Code: Select all

```
0.0000000
0.0000000
0.0000001
0.0000014
0.0002656
0.1134627
0.6651364
0.9768651
0.9998338
0.9999998
0.9999999
1.0000000
1.0000000
1.0000000
1.0000000
1.0000000
```

Posted: **Sat Jun 12, 2004 1:41 am**

by **misof**

to shuniu:

first: I used double too, got AC.

second: 100 0 is not a valid input (zero boxes?)

third: Your outputs are correct, the formatting isn't. Read output description carefully.

Posted: **Mon Jun 14, 2004 4:32 pm**

by **shuniu**

thanks, misof, i get AC after i fix that mistake.

btw, i was just trying to be extra careful on the boundary case (0 box), cause the problem never mentioned m>0, and you know how alot of problems try to screw people on such cases.

### SAMPLE INPUT / OUTPUT

Posted: **Wed Jul 13, 2005 5:44 pm**

by **Sedefcho**

INPUT

Code: Select all

```
50 12
100 99
100 100
90 11
29 13
55 52
47 9
98 96
-1
```

OUTPUT

Code: Select all

```
Case 1: 0.1476651
Case 2: 0.9999149
Case 3: 1.0000000
Case 4: 0.0020696
Case 5: 0.7881958
Case 6: 1.0000000
Case 7: 0.0352208
Case 8: 0.9999526
```

Posted: **Fri Dec 23, 2005 5:24 pm**

by **Larry**

If you had 2 chocolates and 2 boxes:

If they were distinguishable (label them A and B), the unique ways to box them are:

[AB] []

[] [AB]

[A] ** **

** [A] **

Thus, the probability that at least one is empty is 1/2.

However, if they were not distnguishable, you would have:

[AA] []

[] [AA]

[A] [A]

Thus, the probability that at least one is empty is 2/3.

Isn't this wrong, because the probability of the events in the latter case don't happen with equal probability..?

It's like flipping a two coin at the same time - there are three distinct outcomes - 2H's, 2T's, and a HT, but that doesn't mean each occurs 1/3 of the time..

### Re: 10648 - Chocolate Box

Posted: **Thu Jul 30, 2009 10:24 am**

by **pradeepr**

I am using long double to store the probabilities of N chocolates being distributed in to M boxes with out leaving any of them empty.

But I am getting precision problems ...

for input N=100 and M=99 , my code outputs 1.0000000 which actually isn't the case.The logic seems to work as evident from outputs for smaller N and M..

I am attaching the code.. Please help me in figuring out whats wrong with this code...

### Re: 10648 - Chocolate Box

Posted: **Thu Jul 30, 2009 10:53 am**

by **mf**

1.0000000 is the correct answer to seven decimal places for n=100 m=99.

### Re: 10648 - Chocolate Box

Posted: **Thu Jul 30, 2009 3:19 pm**

by **pradeepr**

@mf thanks a lot.. I was confused by the input outputs given earlier.