4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <sstream>
4fd800b3a8 2011-02-23        kinaba: #include <iomanip>
4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <map>
4fd800b3a8 2011-02-23        kinaba: #include <set>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: #include <numeric>
4fd800b3a8 2011-02-23        kinaba: #include <iterator>
4fd800b3a8 2011-02-23        kinaba: #include <functional>
4fd800b3a8 2011-02-23        kinaba: #include <complex>
4fd800b3a8 2011-02-23        kinaba: #include <queue>
4fd800b3a8 2011-02-23        kinaba: #include <stack>
4fd800b3a8 2011-02-23        kinaba: #include <cmath>
4fd800b3a8 2011-02-23        kinaba: #include <cassert>
4fd800b3a8 2011-02-23        kinaba: #include <cstring>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: typedef long long LL;
4fd800b3a8 2011-02-23        kinaba: typedef complex<double> CMP;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<typename T>
4fd800b3a8 2011-02-23        kinaba: class IdGen
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	map<T, int> v2id_;
4fd800b3a8 2011-02-23        kinaba: 	vector<T>   id2v_;
4fd800b3a8 2011-02-23        kinaba: public:
4fd800b3a8 2011-02-23        kinaba: 	int v2id(const T& v) {
4fd800b3a8 2011-02-23        kinaba: 		if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
4fd800b3a8 2011-02-23        kinaba: 		return v2id_[v];
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	const T& id2v(int i) const { return id2v_[i]; }
4fd800b3a8 2011-02-23        kinaba: 	int size() const { return id2v_.size(); }
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<typename Vert, typename Cost, typename Flow, int NV=256>
4fd800b3a8 2011-02-23        kinaba: class MinCostFlow
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	IdGen<Vert> idgen;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	vector<int> G[NV];
4fd800b3a8 2011-02-23        kinaba: 	Flow F[NV][NV];
4fd800b3a8 2011-02-23        kinaba: 	Cost C[NV][NV];
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: public:
4fd800b3a8 2011-02-23        kinaba: 	void addEdge( Vert s_, Vert t_, Cost c, Flow f )
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int s = idgen.v2id(s_), t = idgen.v2id(t_);
4fd800b3a8 2011-02-23        kinaba: 		G[s].push_back(t);
4fd800b3a8 2011-02-23        kinaba: 		G[t].push_back(s);
4fd800b3a8 2011-02-23        kinaba: 		C[s][t] = c;
4fd800b3a8 2011-02-23        kinaba: 		C[t][s] = -c;
4fd800b3a8 2011-02-23        kinaba: 		F[s][t] = f;
4fd800b3a8 2011-02-23        kinaba: 		F[t][s] = 0;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	pair<Cost, Flow> calc( Vert s_, Vert t_ )
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_);
4fd800b3a8 2011-02-23        kinaba: 		static const Cost COST_INF = 1e+300; // !!EDIT HERE!!
4fd800b3a8 2011-02-23        kinaba: 		static const Flow FLOW_INF = 0x7fffffff;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		Cost total_cost = 0;
4fd800b3a8 2011-02-23        kinaba: 		Flow total_flow = 0;
524cc07867 2012-04-03        kinaba: 		vector<Cost> dist(N, 0); // Distance from S : initially unknown.
524cc07867 2012-04-03        kinaba: 		for(;;)
4fd800b3a8 2011-02-23        kinaba: 		{
524cc07867 2012-04-03        kinaba: 			// Dijkstra : find the "shortest path" from S to T wrt C[][].
524cc07867 2012-04-03        kinaba: 			//   C[][] can be <0 so we must be careful. Instead of computing the shortest path directly,
524cc07867 2012-04-03        kinaba: 			//   we compute the increase ("delta") from the shortest path in the previous iteration.
524cc07867 2012-04-03        kinaba: 			//   Since shortest path cannot decrease, delta is always >=0 when traversing edges.
524cc07867 2012-04-03        kinaba: 			//   Smallest delta implies smallest dist[T]+delta[T].
524cc07867 2012-04-03        kinaba: 			vector<Cost> delta(N, COST_INF); delta[S] = 0;
4fd800b3a8 2011-02-23        kinaba: 			vector<int>  prev(N, -1);
4fd800b3a8 2011-02-23        kinaba: 
524cc07867 2012-04-03        kinaba: 			typedef pair< Cost, pair<int, int> > cedge;
4fd800b3a8 2011-02-23        kinaba: 			priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
524cc07867 2012-04-03        kinaba: 			Q.push( cedge(0, make_pair(S, S)) );
4fd800b3a8 2011-02-23        kinaba: 			while( !Q.empty() ) {
524cc07867 2012-04-03        kinaba: 				const cedge e = Q.top(); Q.pop();
524cc07867 2012-04-03        kinaba: 				const int u_prev = e.second.first;
524cc07867 2012-04-03        kinaba: 				const int u = e.second.second;
524cc07867 2012-04-03        kinaba: 				if( prev[u] >= 0 ) // visited
4fd800b3a8 2011-02-23        kinaba: 					continue;
524cc07867 2012-04-03        kinaba: 				prev[u] = u_prev;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 				for(int i=0; i<G[u].size(); ++i) {
524cc07867 2012-04-03        kinaba: 					const int  v = G[u][i];
524cc07867 2012-04-03        kinaba: 					const Cost v_delta = dist[u]+delta[u]+C[u][v] - dist[v];
524cc07867 2012-04-03        kinaba: 					if( F[u][v]>0 && delta[v]>v_delta )
524cc07867 2012-04-03        kinaba: 						Q.push( cedge(delta[v]=v_delta, make_pair(u,v)) );
4fd800b3a8 2011-02-23        kinaba: 				}
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 
524cc07867 2012-04-03        kinaba: 			// If T is unreachable, finished.
4fd800b3a8 2011-02-23        kinaba: 			if( prev[T] < 0 )
524cc07867 2012-04-03        kinaba: 				break;
524cc07867 2012-04-03        kinaba: 
524cc07867 2012-04-03        kinaba: 			// Update the distance table.
524cc07867 2012-04-03        kinaba: 			for(int u=0; u<N; ++u)
524cc07867 2012-04-03        kinaba: 				if( delta[u] != COST_INF )
524cc07867 2012-04-03        kinaba: 					dist[u] += delta[u];
4fd800b3a8 2011-02-23        kinaba: 
524cc07867 2012-04-03        kinaba: 			// How much water can flow on the min-cost path?
524cc07867 2012-04-03        kinaba: 			Flow f = FLOW_INF;
4fd800b3a8 2011-02-23        kinaba: 			for(int u=T; u!=S; u=prev[u])
4fd800b3a8 2011-02-23        kinaba: 				f = min(f, F[prev[u]][u]);
4fd800b3a8 2011-02-23        kinaba: 
524cc07867 2012-04-03        kinaba: 			// Run the flow as much as possible
524cc07867 2012-04-03        kinaba: 			total_flow += f;
524cc07867 2012-04-03        kinaba: 			for(int u=T; u!=S; u=prev[u]) {
4fd800b3a8 2011-02-23        kinaba: 				total_cost    += f * C[prev[u]][u];
4fd800b3a8 2011-02-23        kinaba: 				F[prev[u]][u] -= f;
4fd800b3a8 2011-02-23        kinaba: 				F[u][prev[u]] += f;
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return make_pair(total_cost, total_flow);
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: class FoxCardGame { public:
4fd800b3a8 2011-02-23        kinaba: 	double theMaxProportion(vector <double> pileA, vector <double> pileB, int k)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		double L=1, R=50;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<50; ++i)
4fd800b3a8 2011-02-23        kinaba: 			(possible(pileA, pileB, k, (L+R)/2) ? L : R) = (L+R)/2;
4fd800b3a8 2011-02-23        kinaba: 		return L;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	enum Tag {Src, Left, Right, Target, Goal};
4fd800b3a8 2011-02-23        kinaba: 	bool possible(vector <double> pileA, vector <double> pileB, int k, double R)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		MinCostFlow<pair<Tag,int>, double, int> mcf;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		for(int a=0; a<pileA.size(); ++a)
4fd800b3a8 2011-02-23        kinaba: 			mcf.addEdge( make_pair(Src,0), make_pair(Left,a), 0.0, 1 );
4fd800b3a8 2011-02-23        kinaba: 		for(int a=0; a<pileA.size(); ++a)
4fd800b3a8 2011-02-23        kinaba: 		for(int b=0; b<pileB.size(); ++b)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			double x_ = pileA[a]+pileB[b], y_ = pileA[a]*pileB[b];
4fd800b3a8 2011-02-23        kinaba: 			double x = max(x_,y_), y = min(x_,y_);
4fd800b3a8 2011-02-23        kinaba: 			mcf.addEdge( make_pair(Left,a), make_pair(Right,b), R*y-x+10000.0, 1 );
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		for(int b=0; b<pileB.size(); ++b)
4fd800b3a8 2011-02-23        kinaba: 			mcf.addEdge( make_pair(Right,b), make_pair(Target,0), 0.0, 1 );
4fd800b3a8 2011-02-23        kinaba: 		mcf.addEdge( make_pair(Target,0), make_pair(Goal,0), 0.0, k );
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		return mcf.calc( make_pair(Src,0), make_pair(Goal,0) ).first <= 10000.0*k;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: // BEGIN CUT HERE
4fd800b3a8 2011-02-23        kinaba: #include <ctime>
4fd800b3a8 2011-02-23        kinaba: double start_time; string timer()
4fd800b3a8 2011-02-23        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
4fd800b3a8 2011-02-23        kinaba:  { os << "{ ";
4fd800b3a8 2011-02-23        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
4fd800b3a8 2011-02-23        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
4fd800b3a8 2011-02-23        kinaba: void verify_case(const double& Expected, const double& Received) {
4fd800b3a8 2011-02-23        kinaba:  bool ok = (abs(Expected - Received) < 1e-9);
4fd800b3a8 2011-02-23        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
4fd800b3a8 2011-02-23        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
4fd800b3a8 2011-02-23        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
4fd800b3a8 2011-02-23        kinaba: #define END	 verify_case(_, FoxCardGame().theMaxProportion(pileA, pileB, k));}
4fd800b3a8 2011-02-23        kinaba: int main(){
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: CASE(0)
4fd800b3a8 2011-02-23        kinaba: 	double pileA_[] = {1, 2, 3};
4fd800b3a8 2011-02-23        kinaba: 	  vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_));
4fd800b3a8 2011-02-23        kinaba: 	double pileB_[] = {4, 5, 6};
4fd800b3a8 2011-02-23        kinaba: 	  vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_));
4fd800b3a8 2011-02-23        kinaba: 	int k = 2;
4fd800b3a8 2011-02-23        kinaba: 	double _ = 1.7692307692309948;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(1)
4fd800b3a8 2011-02-23        kinaba: 	double pileA_[] = {1.234, 5.678, 9.012, 3.456, 7.89};
4fd800b3a8 2011-02-23        kinaba: 	  vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_));
4fd800b3a8 2011-02-23        kinaba: 	double pileB_[] = {2.345, 6.789, 9.876, 5.432, 1.012};
4fd800b3a8 2011-02-23        kinaba: 	  vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_));
4fd800b3a8 2011-02-23        kinaba: 	int k = 3;
4fd800b3a8 2011-02-23        kinaba: 	double _ = 4.159424420079586;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(2)
4fd800b3a8 2011-02-23        kinaba: 	double pileA_[] = {1, 1.1, 1.2, 1.3, 1.4, 1.5};
4fd800b3a8 2011-02-23        kinaba: 	  vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_));
4fd800b3a8 2011-02-23        kinaba: 	double pileB_[] = {5, 10, 15, 20, 25, 30};
4fd800b3a8 2011-02-23        kinaba: 	  vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_));
4fd800b3a8 2011-02-23        kinaba: 	int k = 2;
4fd800b3a8 2011-02-23        kinaba: 	double _ = 1.3972602739726827;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(3)
4fd800b3a8 2011-02-23        kinaba: 	double pileA_[] = {85.302, 92.798, 76.813, 37.994, 36.737, 98.659};
4fd800b3a8 2011-02-23        kinaba: 	  vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_));
4fd800b3a8 2011-02-23        kinaba: 	double pileB_[] = {13.352, 7.3094, 54.761, 8.2706, 63.223, 37.486};
4fd800b3a8 2011-02-23        kinaba: 	  vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_));
4fd800b3a8 2011-02-23        kinaba: 	int k = 3;
4fd800b3a8 2011-02-23        kinaba: 	double _ = 33.58603889836175;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(4)
4fd800b3a8 2011-02-23        kinaba: 	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};
4fd800b3a8 2011-02-23        kinaba: 	  vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_));
4fd800b3a8 2011-02-23        kinaba: 	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};
4fd800b3a8 2011-02-23        kinaba: 	  vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_));
4fd800b3a8 2011-02-23        kinaba: 	int k = 50;
4fd800b3a8 2011-02-23        kinaba: 	double _ = 16.846938775510203;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(5)
524cc07867 2012-04-03        kinaba: 	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};
4fd800b3a8 2011-02-23        kinaba: 	  vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_));
524cc07867 2012-04-03        kinaba: 	double pileB_[] = {51.0, 52.0, 53.0, 54.0, 55.0, 56.0, 57.0, 58.0, 59.0, 60.0, 61.0, 62.0, 63.0, 64.0, 65.0, 66.0, 67.0, 68.0, 69.0, 70.0, 71.0, 72.0, 73.0, 74.0, 75.0, 76.0, 77.0, 78.0, 79.0, 80.0, 81.0, 82.0, 83.0, 84.0, 85.0, 86.0, 87.0, 88.0, 89.0, 90.0, 91.0, 92.0, 93.0, 94.0, 95.0, 96.0, 97.0, 98.0, 99.0, 100.0};
4fd800b3a8 2011-02-23        kinaba: 	  vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_));
524cc07867 2012-04-03        kinaba: 	int k = 50;
524cc07867 2012-04-03        kinaba: 	double _ = 21.128144186967717;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: // END CUT HERE
524cc07867 2012-04-03        kinaba: