/* Topcoder SRM 702, D2, 1000-pointer: SubsetSumExtreme.
   James S. Plank
   November 20, 2016
 */

#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class SubsetSumExtreme {
  public:
    vector <int> SizesOfSets;                  /* For each set, this is the sum of its blocks. */
    vector < vector <int> > SetsBySize;      /* All of the sets that have the same size. */
    vector <int> F;                          /* This is a copy of "face". */
    vector <double> Cache;                   /* The memoization cache. */

    double GE(int setid);
    double getExpectation(vector <int> block, vector <int> face);
};

double SubsetSumExtreme::GE(int s)
{
                    /* These variable names follow the writeup: */
  double sum;       /* This is the sum for the expected value computation. */
  int x;            /* This is the sum of the blocks in s */
  int f;            /* This is the face of the die that we are currently considering. */
  int t;            /* This holds set ids of sets whose blocks sum to x-f. */
  
  double best;      /* For each value of f, this is the best way to do x-f */

  int i, j;         /* These are temporary variables. */
  double r;

  if (s == 0) return 0;
  if (Cache[s] >= 0) return Cache[s];

  sum = 0;
  x = SizesOfSets[s];

  /* For each face f on the die: */

  for (i = 0; i < F.size(); i++) {

    /* Look at each set t whose blocks sum to x-f. */

    f = F[i];
    best = x;
    if (x-f >= 0) {
      for (j = 0; j < SetsBySize[x-f].size(); j++) {
        t = SetsBySize[x-f][j];

        /* If t is a proper subset of s, then call GE recursively. */

        if ((s & t) == t) {
          r = GE(t);
          if (r < best) best = r;
        } 
      }
    }

    /* Add the best answer for f to the sum. */

    sum += best;
  }

  /* At the end, divide sum by F.size() to complete the expected value computation. */

  sum /= (double) F.size();
  Cache[s] = sum;
  return sum;
}

double SubsetSumExtreme::getExpectation(vector <int> B, vector <int> face)
{
  int i, j;
  int sum;

  F = face;

  /* Do a power set enumeration to enumerate all subsets of the blocks.  
     In this enumeration, you're going to set all of the values of
     SizesOfSets and SetsBySize. */

  SetsBySize.resize(1000*12+1);

  for (i = 0; i < (1 << B.size()); i++) {
    sum = 0;
    for (j = 0; j < B.size(); j++) {
      if (i & (1 << j)) {
        sum += B[j];
      }
    }
    SizesOfSets.push_back(sum);
    SetsBySize[sum].push_back(i);
  }

  /* This loop prints out SetsBySize, in case you want to see it. 

  for (i = 0; i < SetsBySize.size(); i++) {
    if (SetsBySize[i].size() > 0) {
      printf("Size: %4d.  Sets:", i);
      for (j = 0; j < SetsBySize[i].size(); j++) printf(" 0x%x", SetsBySize[i][j]);
      printf("\n"); 
    }
  }
  */

  /* Set the memoization cache, and then call GE() on the set which contains
     all of the blocks. */

  Cache.resize(1 << B.size(), -1);
  return GE( (1 << B.size()) - 1 );
}