gistfile1.cpp

#include <iostream>
#include <sstream>
#include <vector>
#include <map>
#include <math.h>
#include <algorithm>
#include <numeric>
#include <bitset>
#include <stack>
#include <queue>
#include <set>
using namespace std;
typedef vector<int> vi;
#define zmax(a, b) (((a) < (b))?(b):(a))
#define zmin(a, b) (((a) < (b))?(a):(b))
#define zabs(a) (((a) < 0)?(-(a)):(a))
#define iif(c, t, f) ((c)?(t):(f))
 
long long gcd(long long a, long long b)
{
  if(b < a) swap(a, b);
  while(a)
  {
    long long c = a;
    a = b % a;
    b = c;
  }
  return b;
}
 
long long lcm(long long a, long long b)
{
  return a / gcd(a, b) * b;
}
 
vector< string > split(string s, string delim)
{
  int last = 0;
  vector<string> ret;
  for(int i = 0; i + delim.size() <= s.size(); i++)
  {
    bool ok = true;
    for(int j = 0; j < delim.size() && ok; j++)
      ok = s[i + j] == delim[j];
    if(ok)
    {
      if(i - last) ret.push_back(s.substr(last, i - last));
      last = i + delim.size();
    }
  }
  if(last < s.size()) ret.push_back(s.substr(last));
  return ret;
}
 
class BigWheels
{
public:
 
  vector< vector< int > > w;
  vector< int > hw;
  double memo[50][101];
 
  double solve(int p, int hspn)
  {
    if(p == w.size()) return 1.0;
  
    double ref = memo[p][hspn];
    if(ref > -0.5) return ref;
    
    ref = 0.0;
    for(int i = 0; i < w[p].size(); i++)
    {
      double prob = 0.0;
      if(w[p][i] > hspn)
        prob = solve(p + 1, w[p][i]);
        
      double prob2 = 0.0;
      int cnt = 0;
      for(int j = 0; j < w[p].size(); j++)
      {
        if(w[p][i] + w[p][j] > hspn && w[p][i] + w[p][j] <= hw[p])
        {
          prob2 += 1.0 / w[p].size() * solve(p + 1, w[p][i] + w[p][j]);
          cnt++;
        }
      }
      
      if(prob2 + 1e-12 >= prob)
      {
        ref += 1.0 / w[p].size() / w[p].size() * ((w[p].size() - cnt) * solve(p + 1, hspn));
      }
      else
      {
        ref += 1.0 / w[p].size() * iif(w[p][i] <= hspn, solve(p + 1, hspn), 0);
      }
    }
    return ref;
  }
  
 
  vector <int> enough(vector <string> wheels)
  {
    int n = wheels.size();
    for(int i = 0; i < n; i++)
    {
      istringstream sin(wheels[i]);
      vector<int> y;
      int x;
      while(sin >> x)
      {
        y.push_back(x);
      }
      sort(y.begin(), y.end());
      w.push_back(y);
      hw.push_back(y[y.size() - 1]);
    }
    
    for(int i = 0; i < 50; i ++) for(int j = 0; j < 101; j++) memo[i][j] = -1.0;
    
    vector<int> x;
    int p = 0;
    for(int i = 0; i < w[p].size(); i++)
    {
      if(i && w[p][i] == w[p][i - 1]) continue;
    
      double prob = 0.0;
      prob = solve(p + 1, w[p][i]);
        
      double prob2 = 0.0;
      for(int j = 0; j < w[p].size(); j++)
      {
        if(w[p][i] + w[p][j] <= hw[p])
        {
          prob2 += 1.0 / w[p].size() * solve(p + 1, w[p][i] + w[p][j]);
        }
      }
      
      cout << "asdf" << i << ", " << prob << ", " << prob2 << endl;
      if(prob2 + 1e-12 < prob) x.push_back(w[p][i]);
    }
    
    return x;
  }
};
 
//Powered by [KawigiEditNonTest] modified by pivanof!