#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
template<typename T>
class IdGen
{
map<T, int> v2id_;
vector<T> id2v_;
public:
int v2id(const T& v) {
if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
return v2id_[v];
}
const T& id2v(int i) const { return id2v_[i]; }
int size() const { return id2v_.size(); }
};
template<typename Vert, typename Cost, typename Flow, int NV=256>
class MinCostFlow
{
IdGen<Vert> idgen;
vector<int> G[NV];
Flow F[NV][NV];
Cost C[NV][NV];
public:
void addEdge( Vert s_, Vert t_, Cost c, Flow f )
{
int s = idgen.v2id(s_), t = idgen.v2id(t_);
G[s].push_back(t);
G[t].push_back(s);
C[s][t] = c;
C[t][s] = -c;
F[s][t] = f;
F[t][s] = 0;
}
pair<Cost, Flow> calc( Vert s_, Vert t_ )
{
const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_);
static const Cost COST_INF = 1e+300; // !!EDIT HERE!!
static const Flow FLOW_INF = 0x7fffffff;
Cost total_cost = 0;
Flow total_flow = 0;
vector<Cost> h(N, 0); // potential
for(Flow RF=FLOW_INF; RF>0; ) // residual flow
{
// Dijkstra -- find the min-cost path
vector<Cost> d(N, COST_INF); d[S] = 0;
vector<int> prev(N, -1);
typedef pair< Cost, pair<int,int> > cedge;
priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
Q.push( cedge(0, make_pair(S,S)) );
while( !Q.empty() ) {
cedge e = Q.top(); Q.pop();
if( prev[e.second.second] >= 0 )
continue;
prev[e.second.second] = e.second.first;
int u = e.second.second;
for(int i=0; i<G[u].size(); ++i) {
int v = G[u][i];
Cost r_cost = C[u][v] + h[u] - h[v];
if( F[u][v] > 0 && d[v] > d[u]+r_cost )
Q.push( cedge(d[v]=d[u]+r_cost, make_pair(u,v)) );
}
}
if( prev[T] < 0 )
break; // Finished
// Run the flow as much as possible
Flow f = RF;
for(int u=T; u!=S; u=prev[u])
f = min(f, F[prev[u]][u]);
RF -= f;
total_flow += f;
for(int u=T; u!=S; u=prev[u])
{
total_cost += f * C[prev[u]][u];
F[prev[u]][u] -= f;
F[u][prev[u]] += f;
}
// Update the potential
for(int u=0; u<N; ++u)
h[u] += d[u];
}
return make_pair(total_cost, total_flow);
}
};
class FoxCardGame { public:
double theMaxProportion(vector <double> pileA, vector <double> pileB, int k)
{
double L=1, R=50;
for(int i=0; i<50; ++i)
(possible(pileA, pileB, k, (L+R)/2) ? L : R) = (L+R)/2;
return L;
}
enum Tag {Src, Left, Right, Target, Goal};
bool possible(vector <double> pileA, vector <double> pileB, int k, double R)
{
MinCostFlow<pair<Tag,int>, double, int> mcf;
for(int a=0; a<pileA.size(); ++a)
mcf.addEdge( make_pair(Src,0), make_pair(Left,a), 0.0, 1 );
for(int a=0; a<pileA.size(); ++a)
for(int b=0; b<pileB.size(); ++b)
{
double x_ = pileA[a]+pileB[b], y_ = pileA[a]*pileB[b];
double x = max(x_,y_), y = min(x_,y_);
mcf.addEdge( make_pair(Left,a), make_pair(Right,b), R*y-x+10000.0, 1 );
}
for(int b=0; b<pileB.size(); ++b)
mcf.addEdge( make_pair(Right,b), make_pair(Target,0), 0.0, 1 );
mcf.addEdge( make_pair(Target,0), make_pair(Goal,0), 0.0, k );
return mcf.calc( make_pair(Src,0), make_pair(Goal,0) ).first <= 10000.0*k;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const double& Expected, const double& Received) {
bool ok = (abs(Expected - Received) < 1e-9);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, FoxCardGame().theMaxProportion(pileA, pileB, k));}
int main(){
CASE(0)
double pileA_[] = {1, 2, 3};
vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_));
double pileB_[] = {4, 5, 6};
vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_));
int k = 2;
double _ = 1.7692307692309948;
END
CASE(1)
double pileA_[] = {1.234, 5.678, 9.012, 3.456, 7.89};
vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_));
double pileB_[] = {2.345, 6.789, 9.876, 5.432, 1.012};
vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_));
int k = 3;
double _ = 4.159424420079586;
END
CASE(2)
double pileA_[] = {1, 1.1, 1.2, 1.3, 1.4, 1.5};
vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_));
double pileB_[] = {5, 10, 15, 20, 25, 30};
vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_));
int k = 2;
double _ = 1.3972602739726827;
END
CASE(3)
double pileA_[] = {85.302, 92.798, 76.813, 37.994, 36.737, 98.659};
vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_));
double pileB_[] = {13.352, 7.3094, 54.761, 8.2706, 63.223, 37.486};
vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_));
int k = 3;
double _ = 33.58603889836175;
END
CASE(4)
double pileA_[] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0, 21.0, 22.0, 23.0, 24.0, 25.0, 26.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0, 33.0, 34.0, 35.0, 36.0, 37.0, 38.0, 39.0, 40.0, 41.0, 42.0, 43.0, 44.0, 45.0, 46.0, 47.0, 48.0, 49.0, 50.0};
vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_));
double pileB_[] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0, 21.0, 22.0, 23.0, 24.0, 25.0, 26.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0, 33.0, 34.0, 35.0, 36.0, 37.0, 38.0, 39.0, 40.0, 41.0, 42.0, 43.0, 44.0, 45.0, 46.0, 47.0, 48.0, 49.0, 50.0};
vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_));
int k = 50;
double _ = 16.846938775510203;
END
/*
CASE(5)
double pileA_[] = ;
vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_));
double pileB_[] = ;
vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_));
int k = ;
double _ = ;
END
*/
}
// END CUT HERE