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: class TheMoviesLevelTwoDivOne { public:
4fd800b3a8 2011-02-23        kinaba: 	vector <int> find(vector <int> length, vector <int> scary)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int N = length.size();
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		vector<int> lwb(N), inc(N);
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<N; ++i)
4fd800b3a8 2011-02-23        kinaba: 			if( scary[i]+47 < length[i] )
4fd800b3a8 2011-02-23        kinaba: 				lwb[i] = length[i] - 47;
4fd800b3a8 2011-02-23        kinaba: 			else
4fd800b3a8 2011-02-23        kinaba: 				lwb[i] = scary[i];
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<N; ++i)
4fd800b3a8 2011-02-23        kinaba: 			inc[i] = 47 - length[i];
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		memo = vector<bool>(1<<N);
4fd800b3a8 2011-02-23        kinaba: 		memo[(1<<N)-1] = true;
4fd800b3a8 2011-02-23        kinaba: 		vector<int> temp;
4fd800b3a8 2011-02-23        kinaba: 		rec(0, 74, N, lwb, inc, temp);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		set<int> not_used;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<N; ++i) not_used.insert(i);
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<result.size(); ++i)
4fd800b3a8 2011-02-23        kinaba: 			not_used.erase(result[i]);
4fd800b3a8 2011-02-23        kinaba: 		result.insert(result.end(), not_used.begin(), not_used.end());
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		return result;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	vector<int>  result;
4fd800b3a8 2011-02-23        kinaba: 	vector<bool> memo;
4fd800b3a8 2011-02-23        kinaba: 	void rec(int mask, int cur, int N, vector<int>& lwb, vector<int>& inc, vector<int>& temp)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		if( result.size() < temp.size() )
4fd800b3a8 2011-02-23        kinaba: 			result = temp;
4fd800b3a8 2011-02-23        kinaba: 		if( memo[mask] )
4fd800b3a8 2011-02-23        kinaba: 			return;
4fd800b3a8 2011-02-23        kinaba: 		memo[mask] = true;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<N; ++i)
4fd800b3a8 2011-02-23        kinaba: 			if( !(mask & (1<<i)) && cur>=lwb[i] )
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				temp.push_back(i);
4fd800b3a8 2011-02-23        kinaba: 				rec(mask|(1<<i), cur+inc[i], N, lwb, inc, temp);
4fd800b3a8 2011-02-23        kinaba: 				temp.pop_back();
4fd800b3a8 2011-02-23        kinaba: 			}
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 vector <int>& Expected, const vector <int>& Received) {
4fd800b3a8 2011-02-23        kinaba:  bool ok = (Expected == Received);
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(_, TheMoviesLevelTwoDivOne().find(length, scary));}
4fd800b3a8 2011-02-23        kinaba: int main(){
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: CASE(0)
4fd800b3a8 2011-02-23        kinaba: 	int length_[] = {100, 50};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_));
4fd800b3a8 2011-02-23        kinaba: 	int scary_[] = {1, 1};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_));
4fd800b3a8 2011-02-23        kinaba: 	int __[] = {0, 1 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(1)
4fd800b3a8 2011-02-23        kinaba: 	int length_[] = {100, 50};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_));
4fd800b3a8 2011-02-23        kinaba: 	int scary_[] = {1, 49};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_));
4fd800b3a8 2011-02-23        kinaba: 	int __[] = {1, 0 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(2)
4fd800b3a8 2011-02-23        kinaba: 	int length_[] = {100, 100, 100, 100};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_));
4fd800b3a8 2011-02-23        kinaba: 	int scary_[] = {77, 76, 75, 74};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_));
4fd800b3a8 2011-02-23        kinaba: 	int __[] = {3, 0, 1, 2 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(3)
4fd800b3a8 2011-02-23        kinaba: 	int length_[] = {100};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_));
4fd800b3a8 2011-02-23        kinaba: 	int scary_[] = {99};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_));
4fd800b3a8 2011-02-23        kinaba: 	int __[] = {0 };
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(4)
4fd800b3a8 2011-02-23        kinaba: 	int length_[] = {2};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_));
4fd800b3a8 2011-02-23        kinaba: 	int scary_[] = {1};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_));
4fd800b3a8 2011-02-23        kinaba: 	  int __[] = {0};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(5)
4fd800b3a8 2011-02-23        kinaba: 	int length_[] = {3};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_));
4fd800b3a8 2011-02-23        kinaba: 	int scary_[] = {1};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_));
4fd800b3a8 2011-02-23        kinaba: 	  int __[] = {0};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(6)
4fd800b3a8 2011-02-23        kinaba:   int length_[] = {5,6,7,8,9,10,11,10,9,8,7,6,5,6,7,8,9,10,11,10};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_));
4fd800b3a8 2011-02-23        kinaba:   int scary_[] = {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_));
4fd800b3a8 2011-02-23        kinaba:   int __[] = {-1};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(7)
4fd800b3a8 2011-02-23        kinaba:   int length_[] = {185, 53, 28, 92, 70};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> length(length_, length_+sizeof(length_)/sizeof(*length_));
4fd800b3a8 2011-02-23        kinaba:   int scary_[] = {96, 17, 4, 6, 34};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> scary(scary_, scary_+sizeof(scary_)/sizeof(*scary_));
4fd800b3a8 2011-02-23        kinaba:   int __[] = {1,2,3,4,0};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> _(__, __+sizeof(__)/sizeof(*__));
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: // END CUT HERE