Advertisement
_rashed

PKU 2096

Jun 27th, 2022
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #define ll long long
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. const int OO = 1e9;
  6. const double EPS = 1e-9;
  7.  
  8. int n,s;
  9. double mem[1001][1001];
  10.  
  11. double solve(int cn, int cs) {
  12.     if(cn == 0 && cs == 0) {
  13.         return 0;
  14.     }
  15.     if(mem[cn][cs] != -1)
  16.         return mem[cn][cs];
  17.     double pn = (1.0*cn)/n;
  18.     double ps = (1.0*cs)/s;
  19.     double &ret = mem[cn][cs];
  20.     ret = 0;
  21.     if(cn > 0 && cs > 0) {
  22.         ret += pn*ps*(1 + solve(cn-1,cs-1));
  23.     }
  24.     if(cn > 0) {
  25.         ret += pn*(1-ps)*(1+solve(cn-1,cs));
  26.     }
  27.     if(cs > 0) {
  28.         ret += (1-pn)*ps*(1+solve(cn,cs-1));
  29.     }
  30.     ret += (1-pn)*(1-ps);
  31.     ret /= (1-(1-pn)*(1-ps));
  32.     return ret;
  33. }
  34.  
  35. int main()
  36. {
  37.     ios_base::sync_with_stdio(false);
  38.     cin.tie(NULL);
  39.     cout.tie(NULL);
  40.     cin >> n >> s;
  41.     for(int i = 0; i <= n; i++) {
  42.         for(int j = 0; j <= s; j++) {
  43.             mem[i][j] = -1;
  44.         }
  45.     }
  46.     cout.precision(4);
  47.     cout << fixed << solve(n,s) << "\n";
  48.     return 0;
  49. }
  50.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement