ahmrf

Untitled

Oct 1st, 2015
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.53 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long   LL;
  6. #define pii         pair<int,int>
  7. #define pll         pair<LL,LL>
  8. #define vi          vector<int>
  9. #define SYNC        ios_base::sync_with_stdio(0)
  10. #define CT          cin.tie(0)
  11. #define sf(a)       scanf("%d", &a)
  12. #define sff(a, b)   scanf("%d %d", &a, &b)
  13. #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
  14. #define debug       printf("Here\n")
  15. #define PI          acos(-1)
  16. #define all(x)      (x.begin(),x.end())
  17. #define mem(x, val) memset((x),val,sizeof((x)))
  18. #define xx          first
  19. #define yy          second
  20. #define pb          push_back
  21. #define _max(a,b,c) max(a, max(b, c))
  22. #define _min(a,b,c) min(a, min(b, c))
  23. #define INF         INT_MAX
  24. #define MOD         1000000007
  25. #define NN          1005
  26.  
  27. int setBit(int n, int pos) { return n = n | (1 << pos); }
  28. int resetBit(int n, int pos) { return n = n & ~(1 << pos); }
  29. bool checkBit(int n, int pos) { return (bool)(n & (1 << pos)); }
  30.  
  31. double dp[NN][NN];
  32.  
  33. double call(int n, int m, int tot) {
  34.     if(n == 0) return 1;
  35.     if(m == 0 && n == 1) return 0;
  36.     if(dp[n][m] != -1) return dp[n][m];
  37.     double ret = 0;
  38.     if(m) ret += ((double) n / (double)tot) * ((double)m / ((double)tot - 1.0)) * call(n, m - 1, tot - 1);
  39.     if(n > 1) ret += ((double) n / (double)tot) * ((double)n - 1.0) / ((double)tot - 1.0) * call(n - 2, m, tot - 2);
  40.     return dp[n][m] = ret;
  41. }
  42.  
  43. int main() {
  44.     for(int i = 0; i < NN; i++)
  45.         for(int j = 0; j < NN; j++)
  46.             dp[i][j] = -1;
  47.     int t, d, T, tt = 1;
  48.     sf(T);
  49.     while(T--) {
  50.         sff(t, d);
  51.         printf("Case %d: %.10lf\n", tt++, call(t, d, t + d + 1));
  52.     }
  53.     return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment