6d771c8da1 2011-07-10        kinaba: #include <iostream>
6d771c8da1 2011-07-10        kinaba: #include <sstream>
6d771c8da1 2011-07-10        kinaba: #include <iomanip>
6d771c8da1 2011-07-10        kinaba: #include <vector>
6d771c8da1 2011-07-10        kinaba: #include <string>
6d771c8da1 2011-07-10        kinaba: #include <map>
6d771c8da1 2011-07-10        kinaba: #include <set>
6d771c8da1 2011-07-10        kinaba: #include <algorithm>
6d771c8da1 2011-07-10        kinaba: #include <numeric>
6d771c8da1 2011-07-10        kinaba: #include <iterator>
6d771c8da1 2011-07-10        kinaba: #include <functional>
6d771c8da1 2011-07-10        kinaba: #include <complex>
6d771c8da1 2011-07-10        kinaba: #include <queue>
6d771c8da1 2011-07-10        kinaba: #include <stack>
6d771c8da1 2011-07-10        kinaba: #include <cmath>
6d771c8da1 2011-07-10        kinaba: #include <cassert>
6d771c8da1 2011-07-10        kinaba: #include <cstring>
6d771c8da1 2011-07-10        kinaba: using namespace std;
6d771c8da1 2011-07-10        kinaba: typedef long long LL;
6d771c8da1 2011-07-10        kinaba: typedef complex<double> CMP;
6d771c8da1 2011-07-10        kinaba: 
6d771c8da1 2011-07-10        kinaba: class PrefixFreeSuperset { public:
6d771c8da1 2011-07-10        kinaba: 	long long minSumLength(vector <string> cur, long long k)
6d771c8da1 2011-07-10        kinaba: 	{
6d771c8da1 2011-07-10        kinaba: 		map<int,LL> open; {
6d771c8da1 2011-07-10        kinaba: 			string me("");
6d771c8da1 2011-07-10        kinaba: 			rec(me, cur, open);
6d771c8da1 2011-07-10        kinaba: 		}
6d771c8da1 2011-07-10        kinaba: 
6d771c8da1 2011-07-10        kinaba: 		LL totalLen = 0;
6d771c8da1 2011-07-10        kinaba: 		for(int i=0; i<cur.size(); ++i)
6d771c8da1 2011-07-10        kinaba: 			totalLen += cur[i].size();
6d771c8da1 2011-07-10        kinaba: 		k -= cur.size();
6d771c8da1 2011-07-10        kinaba: 
6d771c8da1 2011-07-10        kinaba: 		while(k) {
6d771c8da1 2011-07-10        kinaba: 			if( open.empty() )
6d771c8da1 2011-07-10        kinaba: 				return -1;
6d771c8da1 2011-07-10        kinaba: 			map<int,LL>::iterator it = open.begin();
6d771c8da1 2011-07-10        kinaba: 			int lll = it->first;
6d771c8da1 2011-07-10        kinaba: 			LL  ccc = it->second;
6d771c8da1 2011-07-10        kinaba: 			open.erase(it);
6d771c8da1 2011-07-10        kinaba: 
6d771c8da1 2011-07-10        kinaba: 			if( k <= ccc ) {
6d771c8da1 2011-07-10        kinaba: 				totalLen += lll*k;
6d771c8da1 2011-07-10        kinaba: 				k         = 0;
6d771c8da1 2011-07-10        kinaba: 			}
6d771c8da1 2011-07-10        kinaba: 			else if( k <= ccc + open[lll+1] ) {
6d771c8da1 2011-07-10        kinaba: 				totalLen += lll*ccc;
6d771c8da1 2011-07-10        kinaba: 				k        -= ccc;
6d771c8da1 2011-07-10        kinaba: 			}
6d771c8da1 2011-07-10        kinaba: 			else if( k <= ccc*2 + open[lll+1] ) {
6d771c8da1 2011-07-10        kinaba: 				LL div = k - (ccc+open[lll+1]);
6d771c8da1 2011-07-10        kinaba: 				open[lll+1] += div*2;
6d771c8da1 2011-07-10        kinaba: 				totalLen += (ccc-div)*lll;
6d771c8da1 2011-07-10        kinaba: 				k        -= (ccc-div);
6d771c8da1 2011-07-10        kinaba: 			}
6d771c8da1 2011-07-10        kinaba: 			else
6d771c8da1 2011-07-10        kinaba: 				open[lll+1] += ccc*2;
6d771c8da1 2011-07-10        kinaba: 		}
6d771c8da1 2011-07-10        kinaba: 		return totalLen;
6d771c8da1 2011-07-10        kinaba: 	}
6d771c8da1 2011-07-10        kinaba: 
6d771c8da1 2011-07-10        kinaba: 	void rec(string& me, const vector<string>& prefix, map<int,LL>& open)
6d771c8da1 2011-07-10        kinaba: 	{
6d771c8da1 2011-07-10        kinaba: 		bool iamprefix = false;
6d771c8da1 2011-07-10        kinaba: 		for(int i=0; i<prefix.size(); ++i)
6d771c8da1 2011-07-10        kinaba: 			if( me == prefix[i] )
6d771c8da1 2011-07-10        kinaba: 				return;
6d771c8da1 2011-07-10        kinaba: 			else if( is_prefix(me, prefix[i]) )
6d771c8da1 2011-07-10        kinaba: 				iamprefix = true;
6d771c8da1 2011-07-10        kinaba: 		if( iamprefix )
6d771c8da1 2011-07-10        kinaba: 		{
6d771c8da1 2011-07-10        kinaba: 			me += '0';
6d771c8da1 2011-07-10        kinaba: 			rec(me, prefix, open);
6d771c8da1 2011-07-10        kinaba: 			me.resize(me.size()-1);
6d771c8da1 2011-07-10        kinaba: 			me += '1';
6d771c8da1 2011-07-10        kinaba: 			rec(me, prefix, open);
6d771c8da1 2011-07-10        kinaba: 			me.resize(me.size()-1);
6d771c8da1 2011-07-10        kinaba: 		}
6d771c8da1 2011-07-10        kinaba: 		else
6d771c8da1 2011-07-10        kinaba: 		{
6d771c8da1 2011-07-10        kinaba: 			open[me.size()] ++;
6d771c8da1 2011-07-10        kinaba: 		}
6d771c8da1 2011-07-10        kinaba: 	}
6d771c8da1 2011-07-10        kinaba: 
6d771c8da1 2011-07-10        kinaba: 	bool is_prefix(const string& s, const string& t)
6d771c8da1 2011-07-10        kinaba: 	{
6d771c8da1 2011-07-10        kinaba: 		return s.size()<=t.size() && s==t.substr(0,s.size());
6d771c8da1 2011-07-10        kinaba: 	}
6d771c8da1 2011-07-10        kinaba: };
6d771c8da1 2011-07-10        kinaba: 
6d771c8da1 2011-07-10        kinaba: // BEGIN CUT HERE
6d771c8da1 2011-07-10        kinaba: #include <ctime>
6d771c8da1 2011-07-10        kinaba: double start_time; string timer()
6d771c8da1 2011-07-10        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
6d771c8da1 2011-07-10        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
6d771c8da1 2011-07-10        kinaba:  { os << "{ ";
6d771c8da1 2011-07-10        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
6d771c8da1 2011-07-10        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
6d771c8da1 2011-07-10        kinaba: void verify_case(const long long& Expected, const long long& Received) {
6d771c8da1 2011-07-10        kinaba:  bool ok = (Expected == Received);
6d771c8da1 2011-07-10        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
6d771c8da1 2011-07-10        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
6d771c8da1 2011-07-10        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
6d771c8da1 2011-07-10        kinaba: #define END	 verify_case(_, PrefixFreeSuperset().minSumLength(cur, k));}
6d771c8da1 2011-07-10        kinaba: int main(){
6d771c8da1 2011-07-10        kinaba: 
6d771c8da1 2011-07-10        kinaba: CASE(0)
6d771c8da1 2011-07-10        kinaba: 	string cur_[] = {"010"};
6d771c8da1 2011-07-10        kinaba: 	  vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
6d771c8da1 2011-07-10        kinaba: 	long long k = 4LL;
6d771c8da1 2011-07-10        kinaba: 	long long _ = 9LL;
6d771c8da1 2011-07-10        kinaba: END
6d771c8da1 2011-07-10        kinaba: CASE(1)
6d771c8da1 2011-07-10        kinaba: 	string cur_[] = {"01","000"};
6d771c8da1 2011-07-10        kinaba: 	  vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
6d771c8da1 2011-07-10        kinaba: 	long long k = 4LL;
6d771c8da1 2011-07-10        kinaba: 	long long _ = 9LL;
6d771c8da1 2011-07-10        kinaba: END
6d771c8da1 2011-07-10        kinaba: CASE(2)
6d771c8da1 2011-07-10        kinaba: 	string cur_[] = {"0011","011110101","11101010111","11101010100000000","11101010100000001111"};
6d771c8da1 2011-07-10        kinaba: 	  vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
6d771c8da1 2011-07-10        kinaba: 	long long k = 1000000000000LL;
6d771c8da1 2011-07-10        kinaba: 	long long _ = 39971901640560LL;
6d771c8da1 2011-07-10        kinaba: END
6d771c8da1 2011-07-10        kinaba: CASE(3)
6d771c8da1 2011-07-10        kinaba: 	string cur_[] = {"010","00","011","1"};
6d771c8da1 2011-07-10        kinaba: 	  vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
6d771c8da1 2011-07-10        kinaba: 	long long k = 4LL;
6d771c8da1 2011-07-10        kinaba: 	long long _ = 9LL;
6d771c8da1 2011-07-10        kinaba: END
6d771c8da1 2011-07-10        kinaba: CASE(4)
6d771c8da1 2011-07-10        kinaba: 	string cur_[] = {"010","00","011","1"};
6d771c8da1 2011-07-10        kinaba: 	  vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
6d771c8da1 2011-07-10        kinaba: 	long long k = 5LL;
6d771c8da1 2011-07-10        kinaba: 	long long _ = -1LL;
6d771c8da1 2011-07-10        kinaba: END
6d771c8da1 2011-07-10        kinaba: CASE(5)
6d771c8da1 2011-07-10        kinaba: 	string cur_[] = {"0011010",
6d771c8da1 2011-07-10        kinaba: "0011011110",
6d771c8da1 2011-07-10        kinaba: "00110111001",
6d771c8da1 2011-07-10        kinaba: "0011011111",
6d771c8da1 2011-07-10        kinaba: "00110111000",
6d771c8da1 2011-07-10        kinaba: };
6d771c8da1 2011-07-10        kinaba: 	  vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
6d771c8da1 2011-07-10        kinaba: 	long long k = 9LL;
6d771c8da1 2011-07-10        kinaba: 	long long _ = 58LL;
6d771c8da1 2011-07-10        kinaba: END
6d771c8da1 2011-07-10        kinaba: /*
6d771c8da1 2011-07-10        kinaba: CASE(6)
6d771c8da1 2011-07-10        kinaba: 	string cur_[] = ;
6d771c8da1 2011-07-10        kinaba: 	  vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
6d771c8da1 2011-07-10        kinaba: 	long long k = LL;
6d771c8da1 2011-07-10        kinaba: 	long long _ = LL;
6d771c8da1 2011-07-10        kinaba: END
6d771c8da1 2011-07-10        kinaba: */
6d771c8da1 2011-07-10        kinaba: }
6d771c8da1 2011-07-10        kinaba: // END CUT HERE