Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1159
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int fastio() { ios_base::sync_with_stdio(false); cout << fixed << setprecision(10); cin.tie(nullptr); return 0; }
int __fastio = fastio();
constexpr int N = 101;
double pascal[N][N]; // n choose k
void initPascal() {
for(int i=0;i < N;i++) {
pascal[i][0] = 1;
for(int j=1;j < =i;j++) {
pascal[i][j] = pascal[i-1][j] + pascal[i-1][j-1];
}
}
}
void solve() {
int m, w, c;
while(cin >> m >> w >> c, (m+w)) {
double res = 0;
double woman = (double)w/(m+w);
double man = 1 - woman;
for(int i=0;i < =c;i+=2) {
int count_woman = c - i;
double prob = pow(woman, count_woman) * pow(man, i); // * note one person is allowed to receive more than once
double ways = pascal[c][i]; // ways to select i candies from c
res += prob*ways;
}
cout << res << "\n";
}
}
int main() {
initPascal();
solve();
}Input
10 20 7
0 0 29
Output
0.5002286
Demonstration
UVA Online Judge solution - 10218 - Let's Dance - UVA Online Judge solution C,C++,Java