#define USECHRONO
#undef HAVE_MPI

#include "eval.hpp"
#include <cassert>
#include <climits>
#include <cstdlib>
#include <stack>
#include <algorithm>
using namespace aed;
using namespace std;


//---:---<*>---:---<*>- COMIENZA CODIGO FUNCION --:---<*>---:---<*>---:---<*>
// COMPLETAR DNI y NOMBRE AQUI:
// Nombre: Varrone, Martina Victoria
int DNI=44022756;

void subconjProp(set<int>&S, list<set<int>>&subS){
  auto itS= S.begin();
  while(itS!= S.end()){
    set<int> x = {*itS};
    set<int> aux;
    set_difference(S,x,aux);
    
    subS.push_back(aux);
    subconjProp(aux,subS);
    ++itS;
  }
}

float calcProm(set<int> &S){
  float suma = 0;
  float size = 0;
  auto it = S.begin();
  while(it!= S.end()){
    suma +=*it;
    ++size;
    ++it;
  }
  float prom;
  prom = suma / size;
  return prom;
}
  
int max_elem(set<int> &S){
  int max = -1000;
  for( auto x : S){
    if(x>max) max =x;
  }
  return max;
}
  
bool R(set<int>&A, set<int>&B){
  
  if(!A.empty() and !B.empty()){ 
  if(A.empty() and !B.empty()) return false;
  if(!A.empty() and B.empty()){
    return true;
  }
  int maxA = max_elem(A);
  int maxB = max_elem(B);
  
  if(maxA > maxB){
    return true;
  }else if(maxA == maxB){
    set<int> A2 = A;
    A2.erase(maxA);
    set<int> B2 = B;
    B2.erase(maxB);
    return R(A2,B2);
  }
    return false;
  }
}

void get_largest_subset(set<int> &S, set<int> &C){
  if(S.empty()) return;
  int prom = calcProm(S);
  
  list<set<int>> subconj;
  subconjProp(S,subconj);

  int dif1 = 100;
  int dif2 = 100;
  set<int> Mayor1;
  set<int> Mayor2;
  
  for( auto s : subconj){
    int promS = calcProm(s);
    if(abs(prom - promS) < dif1){
      Mayor1 = s;
      dif1 = abs(prom - promS);
    }else if(abs(prom - promS) < dif2){
      Mayor2 = s;
      dif2 = abs(prom - promS);
    }
  }
  
  if(dif1>dif2){
    C = Mayor1;
    return;
  }
  if(dif1<dif2){
    C = Mayor2;
    return;
  }
  
  if(R(Mayor1,Mayor2)){
    C = Mayor1;
  }else{
    C = Mayor2;
  }
  
}


//---:---<*>---:---<*>- FINALIZA CODIGO FUNCION --:---<*>---:---<*>---:---<*>
int main() {
  Eval ev;
  int vrbs=0;
  ev.eval<1>(get_largest_subset,vrbs);
  
  return 0;
}