Artifact be660a3b96dfe736312dfc6bd45d4cce952ef505

• File SRM/344/1B.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
typedef long long LL;

class QuantumAlchemy
{
public:
	int minSteps(string initial, vector <string> reactions) 
	{
		map<char, string> r;
		for(int i=0; i<reactions.size(); ++i)
		{
			int j = reactions[i].find('-');
			r[reactions[i][j+2]] = reactions[i].substr(0, j);
		}

		map<char, int> g;
		for(int i=0; i<initial.size(); ++i)
			g[initial[i]]++;

		if( g['X'] )
			return 0;
		set<char> stk; stk.insert('X');
		return make('X', r, g, stk);
	}

	int make(char X, map<char,string>& r, map<char, int>& g, set<char>& stk)
	{
		if( !r.count(X) )
			return -1;
		string s = r[X];

		int rea = 1;
		for(int i=0; i<s.size(); ++i)
			if( g[s[i]] )
				g[s[i]]--;
			else {
				if( stk.count(s[i]) )
					return -1;
				stk.insert(s[i]);
				int subrea = make(s[i], r, g, stk);
				stk.erase(s[i]);
				if( subrea == -1 )
					return -1;
				rea += subrea;
			}
		return rea;
	}

// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { string Arg0 = "ABCDE"; string Arr1[] = {"ABC->F", "FE->X"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 2; verify_case(0, Arg2, minSteps(Arg0, Arg1)); }
	void test_case_1() { string Arg0 = "AABBB"; string Arr1[] = {"BZ->Y", "ZY->X", "AB->Z"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 4; verify_case(1, Arg2, minSteps(Arg0, Arg1)); }
	void test_case_2() { string Arg0 = "AAABB"; string Arr1[] = {"BZ->Y", "ZY->X", "AB->Z"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = -1; verify_case(2, Arg2, minSteps(Arg0, Arg1)); }
	void test_case_3() { string Arg0 = "AAXB"; string Arr1[] = {"BZ->Y", "ZY->X", "AB->Z"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 0; verify_case(3, Arg2, minSteps(Arg0, Arg1)); }
	void test_case_4() { string Arg0 = "ABCDEFGHIJKLMNOPQRSTUVWYZABCDEFGHIJKLMNOPQRSTUVWYZ"; string Arr1[] = {"ABCE->Z", "RTYUIO->P", "QWER->T", "MN->B"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = -1; verify_case(4, Arg2, minSteps(Arg0, Arg1)); }

// END CUT HERE
};
// BEGIN CUT HERE 
int main() {
	QuantumAlchemy().run_test(-1);
}
// END CUT HERE