Fshl0

Averaging the Average

Sep 11th, 2021
905
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 34;
  6.  
  7. int A[N], dp[2][N][N][101][101];
  8.  
  9. int main () {
  10.     int n, k, total = 0;
  11.     cin >> n >> k;
  12.    
  13.     for (int i = 0; i < n; i++) {
  14.         cin >> A[i];
  15.         total += A[i];
  16.     }
  17.    
  18.     dp[0][0][0][0][0] = true;
  19.     for (int i = 0; i < n; i++) {
  20.         for (int j = 0; j <= i; j++) {
  21.             for (int z = 0; z <= i; z++) {
  22.                 for (int l = 0; l <= 100; l++) {
  23.                     for (int m = 0; m <= 100; m++) {
  24.                         dp[(i + 1) & 1][j + 1][z][l + A[i]][m] |= dp[i & 1][j][z][l][m];
  25.                         dp[(i + 1) & 1][j][z + 1][l][m + A[i]] |= dp[i & 1][j][z][l][m];
  26.                         dp[(i + 1) & 1][j][z][l][m] |= dp[i & 1][j][z][l][m];
  27.                     }
  28.                 }
  29.             }
  30.         }
  31.     }
  32.    
  33.     int num = 0, den = 1;
  34.     int diffNum = k, diffDen = 1;
  35.     for (int i = 1; i < n; i++) {
  36.         for (int j = 1; j < n; j++) {
  37.             int z = n - i - j;
  38.  
  39.             if (z <= 0)
  40.                 continue;
  41.                
  42.             for (int c1 = 1; c1 < 100; c1++) {
  43.                 for (int c2 = 1; c2 < 100; c2++) {
  44.                     int c3 = total - c1 - c2;
  45.                    
  46.                     if (!dp[n & 1][i][j][c1][c2])
  47.                         continue;
  48.                    
  49.                     int tmpNum = j * z * c1 + i * z * c2 + i * j * c3;
  50.                     int tmpDen = 3 * i * j * z;
  51.                     int tmp = abs (tmpNum - k * i * j * z * 3);
  52.                    
  53.                     if (tmp * diffDen < tmpDen * diffNum) {
  54.                         diffNum = tmp, diffDen = tmpDen;
  55.                         num = tmpNum, den = tmpDen;
  56.                     } else if (tmp * diffDen == tmpDen * diffNum && tmpNum < 3 * k * i * j * z) {
  57.                         diffNum = tmp, diffDen = tmpDen;
  58.                         num = tmpNum, den = tmpDen;
  59.                     }
  60.                 }
  61.             }
  62.         }
  63.     }
  64.    
  65.     int g = __gcd (num, den);
  66.     cout << num / g << '/' << den / g << "\n";
  67.    
  68.     return 0;
  69. }
  70.  
RAW Paste Data