24h購物| | PChome| 登入
2013-08-11 16:56:21| 人氣1,923| 回應0 | 上一篇 | 下一篇

[UVA][dp] 10218 - Let's Dance !!!

推薦 0 收藏 0 轉貼0 訂閱站台

Problem L
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 20
10 20 7
0 0 29

 

Sample Output:

0.5000000
0.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;
}

台長: Morris
人氣(1,923) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA] 11021 - Tribles
此分類上一篇:[UVA] 11816 - HST

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文