fork(1) 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. long double solve(int i, int rem)
  74. {
  75.     if (i == m)
  76.     {
  77.         int usedCandy = c - rem;
  78.         return (!(usedCandy&1));
  79.     }
  80.     long double &ret = dp[i][rem];
  81.     if (ret == ret)
  82.         return ret;
  83.     ret = 0;
  84.     for (int tk = 0; tk <= rem; ++tk)
  85.     {
  86.         ret += C[rem][tk] * power(p, tk) * power(1.0 - p, rem - tk) * solve(i + 1, rem - tk);
  87.     }
  88.     return ret;
  89. }
  90.  
  91.  
  92. int main()
  93. {
  94.     ios_base::sync_with_stdio(false);
  95.     cin.tie(0);
  96.     cout.tie(0);
  97. #ifndef ONLINE_JUDGE
  98.     freopen("input.txt", "r", stdin);
  99. //    freopen("facebook.txt", "w", stdout);
  100. #endif
  101.     genC();
  102.     while (cin >> m >> w >> c && (m || w))
  103.     {
  104.         clr(dp, -1);
  105.         p = 1.0/(m+w); // probability for a person to get a single candy
  106.         cout << fixed << setprecision(7) << solve(0, c) << '\n';
  107.     }
  108.     return  0;
  109.  
  110. }
Success #stdin #stdout 0s 17056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AjdoVF
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!