2de557d8c0 2011-03-20        kinaba: #include <iostream>
2de557d8c0 2011-03-20        kinaba: #include <sstream>
2de557d8c0 2011-03-20        kinaba: #include <iomanip>
2de557d8c0 2011-03-20        kinaba: #include <vector>
2de557d8c0 2011-03-20        kinaba: #include <string>
2de557d8c0 2011-03-20        kinaba: #include <map>
2de557d8c0 2011-03-20        kinaba: #include <set>
2de557d8c0 2011-03-20        kinaba: #include <algorithm>
2de557d8c0 2011-03-20        kinaba: #include <numeric>
2de557d8c0 2011-03-20        kinaba: #include <iterator>
2de557d8c0 2011-03-20        kinaba: #include <functional>
2de557d8c0 2011-03-20        kinaba: #include <complex>
2de557d8c0 2011-03-20        kinaba: #include <queue>
2de557d8c0 2011-03-20        kinaba: #include <stack>
2de557d8c0 2011-03-20        kinaba: #include <cmath>
2de557d8c0 2011-03-20        kinaba: #include <cassert>
2de557d8c0 2011-03-20        kinaba: #include <cstring>
2de557d8c0 2011-03-20        kinaba: using namespace std;
2de557d8c0 2011-03-20        kinaba: typedef long long LL;
2de557d8c0 2011-03-20        kinaba: typedef complex<double> CMP;
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: template<typename V>
2de557d8c0 2011-03-20        kinaba: class Graph
2de557d8c0 2011-03-20        kinaba: {
2de557d8c0 2011-03-20        kinaba: 	map<V, int> v2id_;
2de557d8c0 2011-03-20        kinaba: 	vector<V>   id2v_;
2de557d8c0 2011-03-20        kinaba: public:
2de557d8c0 2011-03-20        kinaba: 	vector< vector<int> > G;
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: 	int vert( const V& t )
2de557d8c0 2011-03-20        kinaba: 	{
2de557d8c0 2011-03-20        kinaba: 		if( !v2id_.count(t) ) { v2id_[t] = G.size(); id2v_.push_back(t); G.resize(G.size()+1); }
2de557d8c0 2011-03-20        kinaba: 		return v2id_[t];
2de557d8c0 2011-03-20        kinaba: 	}
2de557d8c0 2011-03-20        kinaba: 	void edge( const V& s_, const V& t_ )
2de557d8c0 2011-03-20        kinaba: 	{
2de557d8c0 2011-03-20        kinaba: 		int s=vert(s_), t=vert(t_);
2de557d8c0 2011-03-20        kinaba: 		G[s].push_back(t);
2de557d8c0 2011-03-20        kinaba: 	}
2de557d8c0 2011-03-20        kinaba: 	const V& orig( int v )
2de557d8c0 2011-03-20        kinaba: 	{
2de557d8c0 2011-03-20        kinaba: 		return id2v_[v];
2de557d8c0 2011-03-20        kinaba: 	}
2de557d8c0 2011-03-20        kinaba: };
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: class StronglyConnectedComponent
2de557d8c0 2011-03-20        kinaba: {
2de557d8c0 2011-03-20        kinaba: public:
2de557d8c0 2011-03-20        kinaba: 	StronglyConnectedComponent( const vector< vector<int> >& G )
2de557d8c0 2011-03-20        kinaba: 		: scc(), forest(), G(G), no(0), dfs_no(G.size()), dfs_lo(G.size()), scc_id(G.size())
2de557d8c0 2011-03-20        kinaba: 	{
2de557d8c0 2011-03-20        kinaba: 		for(int v=0; v<G.size(); ++v)
2de557d8c0 2011-03-20        kinaba: 			dfs(v);
2de557d8c0 2011-03-20        kinaba: 	}
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: 	vector< vector<int> > scc;    // scc[i] : the list of verts in the i-th component
2de557d8c0 2011-03-20        kinaba: 	vector< vector<int> > forest; // the forest structure over sccs
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: private:
2de557d8c0 2011-03-20        kinaba: 	const vector< vector<int> >& G;
2de557d8c0 2011-03-20        kinaba: 	int no;
2de557d8c0 2011-03-20        kinaba: 	vector<int> dfs_no; // Special: 0       : not visited yet
2de557d8c0 2011-03-20        kinaba: 	vector<int> dfs_lo; // Special: INT_MAX : already classified into some scc !!!! not a good idea!
2de557d8c0 2011-03-20        kinaba: 	// rather use scc_id for that purpose (distinguishing assigned or not)
2de557d8c0 2011-03-20        kinaba: 	vector<int> scc_id;
2de557d8c0 2011-03-20        kinaba: 	vector<int> pending;
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: 	void dfs(int v)
2de557d8c0 2011-03-20        kinaba: 	{
2de557d8c0 2011-03-20        kinaba: 		if( dfs_no[v] )
2de557d8c0 2011-03-20        kinaba: 			return;
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: 		dfs_no[v] = dfs_lo[v] = ++no;    // visit v
2de557d8c0 2011-03-20        kinaba: 		for(int i=0; i<G[v].size(); ++i) // visit children
2de557d8c0 2011-03-20        kinaba: 		{
2de557d8c0 2011-03-20        kinaba: 			int u = G[v][i];
2de557d8c0 2011-03-20        kinaba: 			dfs( u );
2de557d8c0 2011-03-20        kinaba: 			if( !is_already_classified_in_some_scc(u) )
2de557d8c0 2011-03-20        kinaba: 				dfs_lo[v] = min( dfs_lo[v], dfs_lo[G[v][i]] );
2de557d8c0 2011-03-20        kinaba: 		}
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: 		pending.push_back(v);
2de557d8c0 2011-03-20        kinaba: 		if( dfs_no[v] == dfs_lo[v] ) { // found the representative of a scc
2de557d8c0 2011-03-20        kinaba: 			// todo: pending -> dfs_lo:=INT_MAX
2de557d8c0 2011-03-20        kinaba: 			scc.push_back(pending), pending.clear();
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: 			// construct scc-forest (if needed)
2de557d8c0 2011-03-20        kinaba: 			scc_id[v] = scc.size()-1;
2de557d8c0 2011-03-20        kinaba: 			set<int> children;
2de557d8c0 2011-03-20        kinaba: 			for(int i=0; i<G[v].size(); ++i)
2de557d8c0 2011-03-20        kinaba: 				if( dfs_lo[G[v][i]] != v )
2de557d8c0 2011-03-20        kinaba: 					children.insert( scc_id[dfs_lo[G[v][i]]] );
2de557d8c0 2011-03-20        kinaba: 			forest.push_back( vector<int>(children.begin(), children.end()) );
2de557d8c0 2011-03-20        kinaba: 		}
2de557d8c0 2011-03-20        kinaba: 	}
2de557d8c0 2011-03-20        kinaba: };
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: class ImpossibleGame { public:
2de557d8c0 2011-03-20        kinaba: 	static LL C(LL n, LL k) {
2de557d8c0 2011-03-20        kinaba: 		LL v = 1;
2de557d8c0 2011-03-20        kinaba: 		for(int i=1; i<=k; ++i)
2de557d8c0 2011-03-20        kinaba: 			v = v * (n+1-i) / i;
2de557d8c0 2011-03-20        kinaba: 		return v;
2de557d8c0 2011-03-20        kinaba: 	}
2de557d8c0 2011-03-20        kinaba: 	static LL weight(LL a, LL b, LL c, LL d) {
2de557d8c0 2011-03-20        kinaba: 		return C(a+b+c+d,a) * C(b+c+d,b) * C(c+d,c);
2de557d8c0 2011-03-20        kinaba: 	}
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: 	long long getMinimum(int k, vector <string> before, vector <string> after)
2de557d8c0 2011-03-20        kinaba: 	{
2de557d8c0 2011-03-20        kinaba: 		vector< pair< vector<int>, vector<int> > > dif;
2de557d8c0 2011-03-20        kinaba: 		for(int i=0; i<after.size(); ++i)
2de557d8c0 2011-03-20        kinaba: 		{
2de557d8c0 2011-03-20        kinaba: 			vector<int> be(4), af(4);
2de557d8c0 2011-03-20        kinaba: 			for(int j=0; j<before[i].size(); ++j) be[before[i][j]-'A'] ++;
2de557d8c0 2011-03-20        kinaba: 			for(int j=0; j< after[i].size(); ++j) af[ after[i][j]-'A'] ++;
2de557d8c0 2011-03-20        kinaba: 			dif.push_back( make_pair(be,af) );
2de557d8c0 2011-03-20        kinaba: 		}
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: 		Graph< vector<int> > G;
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: 		vector<int> v(4);
2de557d8c0 2011-03-20        kinaba: 		for(v[0]=0; v[0]<=k; ++v[0])
2de557d8c0 2011-03-20        kinaba: 		for(v[1]=0; v[0]+v[1]<=k; ++v[1])
2de557d8c0 2011-03-20        kinaba: 		for(v[2]=0; v[0]+v[1]+v[2]<=k; ++v[2])
2de557d8c0 2011-03-20        kinaba: 		for(v[3]=0; v[0]+v[1]+v[2]+v[3]<=k; ++v[3])
2de557d8c0 2011-03-20        kinaba: 		{
2de557d8c0 2011-03-20        kinaba: 			G.vert(v);
2de557d8c0 2011-03-20        kinaba: 			for(int i=0; i<dif.size(); ++i)
2de557d8c0 2011-03-20        kinaba: 			{
2de557d8c0 2011-03-20        kinaba: 				bool dame = false;
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: 				vector<int> u = v;
2de557d8c0 2011-03-20        kinaba: 				for(int k=0; k<4; ++k)
2de557d8c0 2011-03-20        kinaba: 				{
2de557d8c0 2011-03-20        kinaba: 					if( (u[k]-=dif[i].first[k]) < 0 )
2de557d8c0 2011-03-20        kinaba: 						dame = true;
2de557d8c0 2011-03-20        kinaba: 					u[k] += dif[i].second[k];
2de557d8c0 2011-03-20        kinaba: 				}
2de557d8c0 2011-03-20        kinaba: 				if( !dame )
2de557d8c0 2011-03-20        kinaba: 					G.edge(v, u);
2de557d8c0 2011-03-20        kinaba: 			}
2de557d8c0 2011-03-20        kinaba: 		}
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: 		StronglyConnectedComponent scc(G.G);
2de557d8c0 2011-03-20        kinaba: 		return 0;
2de557d8c0 2011-03-20        kinaba: 	}
2de557d8c0 2011-03-20        kinaba: };
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: // BEGIN CUT HERE
2de557d8c0 2011-03-20        kinaba: #include <ctime>
2de557d8c0 2011-03-20        kinaba: double start_time; string timer()
2de557d8c0 2011-03-20        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
2de557d8c0 2011-03-20        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
2de557d8c0 2011-03-20        kinaba:  { os << "{ ";
2de557d8c0 2011-03-20        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
2de557d8c0 2011-03-20        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
2de557d8c0 2011-03-20        kinaba: void verify_case(const long long& Expected, const long long& Received) {
2de557d8c0 2011-03-20        kinaba:  bool ok = (Expected == Received);
2de557d8c0 2011-03-20        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
2de557d8c0 2011-03-20        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
2de557d8c0 2011-03-20        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
2de557d8c0 2011-03-20        kinaba: #define END	 verify_case(_, ImpossibleGame().getMinimum(k, before, after));}
2de557d8c0 2011-03-20        kinaba: int main(){
2de557d8c0 2011-03-20        kinaba: 
2de557d8c0 2011-03-20        kinaba: CASE(0)
2de557d8c0 2011-03-20        kinaba: 	int k = 1;
2de557d8c0 2011-03-20        kinaba: 	string before_[] = { "A" }
2de557d8c0 2011-03-20        kinaba: ;
2de557d8c0 2011-03-20        kinaba: 	  vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
2de557d8c0 2011-03-20        kinaba: 	string after_[] = { "B" }
2de557d8c0 2011-03-20        kinaba: ;
2de557d8c0 2011-03-20        kinaba: 	  vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
2de557d8c0 2011-03-20        kinaba: 	long long _ = 2LL;
2de557d8c0 2011-03-20        kinaba: END
2de557d8c0 2011-03-20        kinaba: CASE(1)
2de557d8c0 2011-03-20        kinaba: 	int k = 2;
2de557d8c0 2011-03-20        kinaba: 	string before_[] = { "A", "A", "D" }
2de557d8c0 2011-03-20        kinaba: ;
2de557d8c0 2011-03-20        kinaba: 	  vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
2de557d8c0 2011-03-20        kinaba: 	string after_[] = { "B", "C", "D" }
2de557d8c0 2011-03-20        kinaba: ;
2de557d8c0 2011-03-20        kinaba: 	  vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
2de557d8c0 2011-03-20        kinaba: 	long long _ = 5LL;
2de557d8c0 2011-03-20        kinaba: END
2de557d8c0 2011-03-20        kinaba: CASE(2)
2de557d8c0 2011-03-20        kinaba: 	int k = 2;
2de557d8c0 2011-03-20        kinaba: 	string before_[] = { "B", "C", "D" }
2de557d8c0 2011-03-20        kinaba: ;
2de557d8c0 2011-03-20        kinaba: 	  vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
2de557d8c0 2011-03-20        kinaba: 	string after_[] = { "C", "D", "B" }
2de557d8c0 2011-03-20        kinaba: ;
2de557d8c0 2011-03-20        kinaba: 	  vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
2de557d8c0 2011-03-20        kinaba: 	long long _ = 9LL;
2de557d8c0 2011-03-20        kinaba: END
2de557d8c0 2011-03-20        kinaba: CASE(3)
2de557d8c0 2011-03-20        kinaba: 	int k = 6;
2de557d8c0 2011-03-20        kinaba: 	string before_[] = { "AABBC", "AAAADA", "AAACA", "CABAA", "AAAAAA", "BAAAA" }
2de557d8c0 2011-03-20        kinaba: ;
2de557d8c0 2011-03-20        kinaba: 	  vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
2de557d8c0 2011-03-20        kinaba: 	string after_[] = { "AACCB", "DAAABC", "AAAAD", "ABCBA", "AABAAA", "AACAA" }
2de557d8c0 2011-03-20        kinaba: ;
2de557d8c0 2011-03-20        kinaba: 	  vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
2de557d8c0 2011-03-20        kinaba: 	long long _ = 499LL;
2de557d8c0 2011-03-20        kinaba: END
2de557d8c0 2011-03-20        kinaba: /*
2de557d8c0 2011-03-20        kinaba: CASE(4)
2de557d8c0 2011-03-20        kinaba: 	int k = ;
2de557d8c0 2011-03-20        kinaba: 	string before_[] = ;
2de557d8c0 2011-03-20        kinaba: 	  vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
2de557d8c0 2011-03-20        kinaba: 	string after_[] = ;
2de557d8c0 2011-03-20        kinaba: 	  vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
2de557d8c0 2011-03-20        kinaba: 	long long _ = LL;
2de557d8c0 2011-03-20        kinaba: END
2de557d8c0 2011-03-20        kinaba: CASE(5)
2de557d8c0 2011-03-20        kinaba: 	int k = ;
2de557d8c0 2011-03-20        kinaba: 	string before_[] = ;
2de557d8c0 2011-03-20        kinaba: 	  vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
2de557d8c0 2011-03-20        kinaba: 	string after_[] = ;
2de557d8c0 2011-03-20        kinaba: 	  vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
2de557d8c0 2011-03-20        kinaba: 	long long _ = LL;
2de557d8c0 2011-03-20        kinaba: END
2de557d8c0 2011-03-20        kinaba: */
2de557d8c0 2011-03-20        kinaba: }
2de557d8c0 2011-03-20        kinaba: // END CUT HERE