fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Sushi {
  5. public:
  6.   double totalOperations(vector<int>& dishes, int n) {
  7.  
  8.     // dp[x][y][z] = expected operations
  9.     vector<vector<vector<double>>> dp(
  10.         n+1, vector<vector<double>>(n+1, vector<double>(n+1, 0.0))
  11.     );
  12.  
  13.     // Count dishes with 1,2,3 sushi
  14.     vector<int> pieces(4, 0);
  15.     for (int x : dishes) pieces[x]++;
  16.  
  17.     int x0 = pieces[1];
  18.     int y0 = pieces[2];
  19.     int z0 = pieces[3];
  20.  
  21.     // Total sushi initially
  22.     int total = x0 + 2*y0 + 3*z0;
  23.  
  24.     // Base case
  25.     dp[0][0][0] = 0.0;
  26.  
  27.     // DP over total sushi
  28.     for (int s = 1; s <= total; s++) {
  29.       for (int z = 0; z <= s / 3; z++) {
  30.         for (int y = 0; y <= (s - 3*z) / 2; y++) {
  31.  
  32.           int x = s - 2*y - 3*z;
  33.           if (x < 0) continue;
  34.           if (x + y + z > n) continue;
  35.  
  36.           int k = x + y + z;
  37.           if (k == 0) continue;
  38.  
  39.           dp[x][y][z] =
  40.               (double)n / k
  41.             + (x ? (double)x / k * dp[x-1][y][z] : 0.0)
  42.             + (y ? (double)y / k * dp[x+1][y-1][z] : 0.0)
  43.             + (z ? (double)z / k * dp[x][y+1][z-1] : 0.0);
  44.         }
  45.       }
  46.     }
  47.  
  48.     // Return expectation from initial state
  49.     return dp[x0][y0][z0];
  50.   }
  51. };
  52.  
  53. int main() {
  54.   int n;
  55.   cin >> n;
  56.  
  57.   vector<int> dishes(n);
  58.   for (int i = 0; i < n; ++i) cin >> dishes[i];
  59.  
  60.   Sushi obj;
  61.   cout << fixed << setprecision(10)
  62.        << obj.totalOperations(dishes, n) << endl;
  63.   return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 5216KB
comments (?)
stdin
copy 
3
1 1 1
stdout
copy 
5.5000000000
https://ideone.com/nyFkU6
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

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!