[UVA][dp] 10218 - Let's Dance !!!
Let's Dance!!
Input: Standard Input
Output: Standard Output
Time Limit: 2 seconds
Consider the following scenario:
You are a University Student; all of your friends consider you courageous, most of the girls find you handsome, you are quite a good student, recently your team has won a regional contest of ACM ICPC and so your confidence is very high. In a party you find someone nice and ask her to dance but she seems smarter than (as always is the case) you. She tells you, “There are M gentle men and W ladies in this party except us. You have C candies in your hand and you distribute them randomly among all these guests (M men and W ladies), of course if possible. Now you collect all the candies from all the gentlemen and this number of candies is CC. If you can evenly distribute these (CC) candies equally between two groups (These two groups are two arbitrary groups) I will dance with you.”
Now tell me what is the probability of her dancing with you?
Input
The input file contains several lines of input. Each line contains three non-negative integers M (M<=1000), W (W<=1000) and C (C<=100). The meanings of the symbols are explained before. The input is terminated by a line where M=0 and W=0. You need not process this input.
Output
For each line of input, you should produce one line of output, which is a floating-point number. This output is the probability of her dancing with you. The number contains seven digits after the decimal point. An error less than 2E-7 or 2* 10^(-7) will be overlooked.
Sample Input:
10 20 2010 20 7
0 0 29
Sample Output:
0.50000000.5002286
Shahriar Manzoor
有 M 個男生，W 個女生，要發送 C 個糖果。每個人最多拿到一個糖果，機率採均勻分布。
給男生們的糖果如果能畫分成兩個相同的堆(即偶數)，這位女生將願意與你跳舞。
問可以跳成的機率為何？
首先對於每個糖果給男生的機率為 p = M/(M+W)
然而只要考慮給男生的糖果個數為奇數還是偶數即可。
考慮兩種情況
dp[i][偶數], dp[i][奇數] : 發送 i 個糖果後，男生拿到偶數、奇數的機率。
依序發送糖果，則
dp[i][偶數] = dp[i-1][奇數]*p + dp[i-1][偶數]*(1-p);
dp[i][奇數] = dp[i-1][偶數]*p + dp[i-1][奇數]*(1-p);
#include <stdio.h>
int main() {
int M, W, C;
int i;
while(scanf("%d %d %d", &M, &W, &C) == 3) {
if(M == 0 && W == 0)
break;
double p = (double)M/(M+W);
double dp[105][2];//[0] even, [1] odd
dp[0][0] = 1, dp[0][1] = 0;
for(i = 1; i <= C; i++) {
dp[i][0] = dp[i-1][1]*p + dp[i-1][0]*(1-p);
dp[i][1] = dp[i-1][0]*p + dp[i-1][1]*(1-p);
}
printf("%.7lf\n", dp[C][0]);
}
return 0;
}