Artifact Content
Not logged in

Artifact c23044dc81c5002a9a1806b85fdc84af206b2a40


#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 V>
class Graph
{
	map<V, int> v2id_;
	vector<V>   id2v_;
public:
	vector< vector<int> > G;

	int vert( const V& t )
	{
		if( !v2id_.count(t) ) { v2id_[t] = G.size(); id2v_.push_back(t); G.resize(G.size()+1); }
		return v2id_[t];
	}
	void edge( const V& s_, const V& t_ )
	{
		int s=vert(s_), t=vert(t_);
		G[s].push_back(t);
	}
	const V& orig( int v )
	{
		return id2v_[v];
	}
};

class StronglyConnectedComponent
{
public:
	StronglyConnectedComponent( const vector< vector<int> >& G )
		: scc(), forest(), G(G), no(0), dfs_no(G.size()), dfs_lo(G.size()), scc_id(G.size())
	{
		for(int v=0; v<G.size(); ++v)
			dfs(v);
	}

	vector< vector<int> > scc;    // scc[i] : the list of verts in the i-th component 
	vector< vector<int> > forest; // the forest structure over sccs

private:
	const vector< vector<int> >& G;
	int no;
	vector<int> dfs_no; // Special: 0       : not visited yet
	vector<int> dfs_lo; // Special: INT_MAX : already classified into some scc !!!! not a good idea!
	// rather use scc_id for that purpose (distinguishing assigned or not)
	vector<int> scc_id;
	vector<int> pending;

	void dfs(int v)
	{
		if( dfs_no[v] )
			return;

		dfs_no[v] = dfs_lo[v] = ++no;    // visit v
		for(int i=0; i<G[v].size(); ++i) // visit children
		{
			int u = G[v][i];
			dfs( u );
			if( !is_already_classified_in_some_scc(u) )
				dfs_lo[v] = min( dfs_lo[v], dfs_lo[G[v][i]] );
		}

		pending.push_back(v);
		if( dfs_no[v] == dfs_lo[v] ) { // found the representative of a scc
			// todo: pending -> dfs_lo:=INT_MAX
			scc.push_back(pending), pending.clear();

			// construct scc-forest (if needed)
			scc_id[v] = scc.size()-1;
			set<int> children;
			for(int i=0; i<G[v].size(); ++i)
				if( dfs_lo[G[v][i]] != v )
					children.insert( scc_id[dfs_lo[G[v][i]]] );
			forest.push_back( vector<int>(children.begin(), children.end()) );
		}
	}
};


class ImpossibleGame { public:
	static LL C(LL n, LL k) {
		LL v = 1;
		for(int i=1; i<=k; ++i)
			v = v * (n+1-i) / i;
		return v;
	}
	static LL weight(LL a, LL b, LL c, LL d) {
		return C(a+b+c+d,a) * C(b+c+d,b) * C(c+d,c);
	}

	long long getMinimum(int k, vector <string> before, vector <string> after) 
	{
		vector< pair< vector<int>, vector<int> > > dif;
		for(int i=0; i<after.size(); ++i)
		{
			vector<int> be(4), af(4);
			for(int j=0; j<before[i].size(); ++j) be[before[i][j]-'A'] ++;
			for(int j=0; j< after[i].size(); ++j) af[ after[i][j]-'A'] ++;
			dif.push_back( make_pair(be,af) );
		}

		Graph< vector<int> > G;

		vector<int> v(4);
		for(v[0]=0; v[0]<=k; ++v[0])
		for(v[1]=0; v[0]+v[1]<=k; ++v[1])
		for(v[2]=0; v[0]+v[1]+v[2]<=k; ++v[2])
		for(v[3]=0; v[0]+v[1]+v[2]+v[3]<=k; ++v[3])
		{
			G.vert(v);
			for(int i=0; i<dif.size(); ++i)
			{
				bool dame = false;

				vector<int> u = v;
				for(int k=0; k<4; ++k)
				{
					if( (u[k]-=dif[i].first[k]) < 0 )
						dame = true;
					u[k] += dif[i].second[k];
				}
				if( !dame )
					G.edge(v, u);
			}
		}

		StronglyConnectedComponent scc(G.G);
		return 0;
	}
};

// 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 long long& Expected, const long long& Received) {
 bool ok = (Expected == Received);
 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(_, ImpossibleGame().getMinimum(k, before, after));}
int main(){

CASE(0)
	int k = 1; 
	string before_[] = { "A" }
;
	  vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_)); 
	string after_[] = { "B" }
;
	  vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 
	long long _ = 2LL; 
END
CASE(1)
	int k = 2; 
	string before_[] = { "A", "A", "D" }
;
	  vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_)); 
	string after_[] = { "B", "C", "D" }
;
	  vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 
	long long _ = 5LL; 
END
CASE(2)
	int k = 2; 
	string before_[] = { "B", "C", "D" }
;
	  vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_)); 
	string after_[] = { "C", "D", "B" }
;
	  vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 
	long long _ = 9LL; 
END
CASE(3)
	int k = 6; 
	string before_[] = { "AABBC", "AAAADA", "AAACA", "CABAA", "AAAAAA", "BAAAA" }
;
	  vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_)); 
	string after_[] = { "AACCB", "DAAABC", "AAAAD", "ABCBA", "AABAAA", "AACAA" }
;
	  vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 
	long long _ = 499LL; 
END
/*
CASE(4)
	int k = ; 
	string before_[] = ;
	  vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_)); 
	string after_[] = ;
	  vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 
	long long _ = LL; 
END
CASE(5)
	int k = ; 
	string before_[] = ;
	  vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_)); 
	string after_[] = ;
	  vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_)); 
	long long _ = LL; 
END
*/
}
// END CUT HERE