[UVA][math] 10648 - Chocolate Box
Input: standard input
Output: standard output
Time Limit: 1 second
Recently one of my friend Tarik became a member of the food committee of an ACM regional competition. He has been given m distinguishable boxes, he has to put n types of chocolates in the boxes. The probability that one chocolate is placed in a certain box is 1 / m. What is the probability that one or more boxes are empty? At first he thought it as an easy task. But soon he found that it was much harder. So, he falls into a great trouble and asked you to help him in this task.
Input
Each line of the input contains
two integers n indicating total number of distinguishable types
of chocolate and m indicating total number of distinguishable
boxes ( m <= n < 100 ). A single line containing
-1 denotes the end.
For each of the cases you should calculate the probability corrected to seven decimal places. The output format is shown below.
Sample Input
50 12
50 12
-1
Sample
Output
Case 1: 0.1476651
Case 2: 0.1476651
Problem Setter: A. K. M. Saifun Nabi (Shabuj) ( BUET PESSIMISTIC )
Thanks to Anupam Bhattacharjee for his alternate solution and data.
dp[i][j] 表示成目前放入第 i 個巧克力，且已經有 j 個箱子被使用。
則有 j/m 的機率維持一樣(仍在原本的 j 個箱子中挑)，
又或者會有 (m-j)/m 的機率會增加一個箱子(挑剩餘的箱子)。
#include <stdio.h>
int main() {
int n, m, cases = 0;
while(scanf("%d %d", &n, &m) == 2) {
double dp[105][105] = {};
int i, j;
dp[0][0] = 1;
for(i = 0; i <= n; i++) {
for(j = 0; j <= m; j++) {
dp[i+1][j] += (dp[i][j] * (j))/m;
dp[i+1][j+1] += (dp[i][j] * (m-j))/m;
}
}
printf("Case %d: %.7lf\n", ++cases, 1 - dp[n][m]);
}
return 0;
}