fork download
copy 
  1. #include<bits/stdc++.h>
  2. //#include <ext/pb_ds/assoc_container.hpp> // Common file
  3. //#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  4.  
  5. using namespace std;
  6. //using namespace __gnu_pbds;
  7. //typedef tree<
  8. //        pair<int, int>, // change type
  9. //        null_type,
  10. //        less<pair<int, int> >, // change type
  11. //        rb_tree_tag,
  12. //        tree_order_statistics_node_update>
  13. //        ordered_set;
  14.  
  15. typedef long long ll;
  16. #define rep(i, start, end) for(int i = start; i < end; ++i)
  17. #define sz(x) (int)(x).size()
  18. #define pb push_back
  19. #define F first
  20. #define S second
  21. #define all(x) x.begin(), x.end()
  22. #define clr(d, v) memset(d, v, sizeof(d))
  23. #define pii pair<int, int>
  24. const double PI = 3.14159265358979323846;
  25. const double eps = (1e-8);
  26.  
  27.  
  28. long double power(long double base, int exp)
  29. {
  30.     long double ret = 1;
  31.     while(exp)
  32.     {
  33.         if (exp&1)
  34.             ret *= base;
  35.         base *= base;
  36.         exp >>= 1;
  37.     }
  38.     return ret;
  39. }
  40.  
  41.  
  42. long double C[105][105];
  43.  
  44. void genC()
  45. {
  46.     C[0][0] = 1;
  47.     for (int i = 1; i <= 100; ++i)
  48.     {
  49.         C[i][0] = 1;
  50.         for (int j = 1; j < i; ++j)
  51.             C[i][j] = C[i-1][j] + C[i-1][j - 1];
  52.         C[i][i] = 1;
  53.     }
  54. }
  55.  
  56. int m, w, c;
  57. long double p;
  58.  
  59. /*
  60.  * i is zero based
  61.  * Dp definition:
  62.  * dp[i][rem] is probability to get a final even 'usedCandy' count in range [i, m) using 'rem' candies such that usedCandy = totalCandies - rem
  63.  * base case:
  64.  * at i == m, return isEven(usedCandy)
  65.  * transition:
  66.  * at each [i][rem], if 'tk' is amount given to man 'i'. 'tk' is in [0, rem]
  67.  * answer = Summation for all 'tk' in [0, rem] -> P(man 'i' getting exactly tk candies) * dp[i + 1][rem - tk]
  68.  * P(a man getting exactly 'tk' candies) having 'rem' candies in total can be found through binomial theorom C[rem][tk] * p^tk * q^(rem - tk) such that p is probability for
  69.  * a person to get a single candy = 1/(m+w) and q = 1 - p 
  70.  */
  71.  
  72. long double dp[1005][105];
  73. bool vis[1005][105];
  74. long double solve(int i, int rem)
  75. {
  76.     if (i == m)
  77.     {
  78.         int usedCandy = c - rem;
  79.         return (!(usedCandy&1));
  80.  
  81.     }
  82.     long double &ret = dp[i][rem];
  83.     if (vis[i][rem])
  84.         return ret;
  85.     vis[i][rem] = 1;
  86.     ret = 0;
  87.     double p = 1.0 / (w + (m-i));
  88.     for (int tk = 0; tk <= rem; ++tk)
  89.     {
  90.         ret += C[rem][tk] * power(p, tk) * power(1.0 - p, rem - tk) * solve(i + 1, rem - tk);
  91.     }
  92.     return ret;
  93. }
  94.  
  95.  
  96. int main()
  97. {
  98.     ios_base::sync_with_stdio(false);
  99.     cin.tie(0);
  100.     cout.tie(0);
  101. #ifndef ONLINE_JUDGE
  102.     freopen("input.txt", "r", stdin);
  103. //    freopen("facebook.txt", "w", stdout);
  104. #endif
  105.     genC();
  106.     while (cin >> m >> w >> c && (m || w))
  107.     {
  108.         clr(vis, 0);
  109.         p = 1.0/(m+w); // probability for a person to get a single candy
  110.         cout << fixed << setprecision(7) << solve(0, c) << '\n';
  111.     }
  112.     return  0;
  113.  
  114. }
Success #stdin #stdout 0s 17160KB
comments (?)
stdin
copy 
10 20 20
10 20 7
0 0 29
stdout
copy 
0.5000000
0.5002286
https://ideone.com/EcZoAV
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!