5cb1f42e86 2016-02-23        kinaba: #include <iostream>
5cb1f42e86 2016-02-23        kinaba: #include <sstream>
5cb1f42e86 2016-02-23        kinaba: #include <iomanip>
5cb1f42e86 2016-02-23        kinaba: #include <vector>
5cb1f42e86 2016-02-23        kinaba: #include <string>
5cb1f42e86 2016-02-23        kinaba: #include <map>
5cb1f42e86 2016-02-23        kinaba: #include <set>
5cb1f42e86 2016-02-23        kinaba: #include <algorithm>
5cb1f42e86 2016-02-23        kinaba: #include <numeric>
5cb1f42e86 2016-02-23        kinaba: #include <iterator>
5cb1f42e86 2016-02-23        kinaba: #include <functional>
5cb1f42e86 2016-02-23        kinaba: #include <complex>
5cb1f42e86 2016-02-23        kinaba: #include <queue>
5cb1f42e86 2016-02-23        kinaba: #include <stack>
5cb1f42e86 2016-02-23        kinaba: #include <cmath>
5cb1f42e86 2016-02-23        kinaba: #include <cassert>
5cb1f42e86 2016-02-23        kinaba: #include <tuple>
5cb1f42e86 2016-02-23        kinaba: using namespace std;
5cb1f42e86 2016-02-23        kinaba: typedef long long LL;
5cb1f42e86 2016-02-23        kinaba: typedef complex<double> CMP;
5cb1f42e86 2016-02-23        kinaba: 
5cb1f42e86 2016-02-23        kinaba: class BearFair { public:
5cb1f42e86 2016-02-23        kinaba: 	string isFair(int n, int b, vector <int> upTo, vector <int> quantity)
5cb1f42e86 2016-02-23        kinaba: 	{
5cb1f42e86 2016-02-23        kinaba: 		return isFair_bool(n, b, upTo, quantity) ? "fair" : "unfair";
5cb1f42e86 2016-02-23        kinaba: 	}
5cb1f42e86 2016-02-23        kinaba: 
5cb1f42e86 2016-02-23        kinaba: 	bool isFair_bool(int n, int b, vector <int> upTo, vector <int> quantity)
5cb1f42e86 2016-02-23        kinaba: 	{
5cb1f42e86 2016-02-23        kinaba: 		set<pair<int,int>> uqs;
5cb1f42e86 2016-02-23        kinaba: 		for(int i=0; i<upTo.size(); ++i)
5cb1f42e86 2016-02-23        kinaba: 			uqs.emplace(upTo[i], quantity[i]);
5cb1f42e86 2016-02-23        kinaba: 		uqs.emplace(b, n);
5cb1f42e86 2016-02-23        kinaba: 		vector<pair<int,int>> uq(uqs.begin(), uqs.end());
5cb1f42e86 2016-02-23        kinaba: 
5cb1f42e86 2016-02-23        kinaba: 		int LastU=0, LastQ=0;
5cb1f42e86 2016-02-23        kinaba: 		set<pair<int,int>> Cand;
5cb1f42e86 2016-02-23        kinaba: 		Cand.emplace(0, 0);
5cb1f42e86 2016-02-23        kinaba: 
5cb1f42e86 2016-02-23        kinaba: 		for(auto& uqi: uq) {
5cb1f42e86 2016-02-23        kinaba: 			int u = uqi.first;
5cb1f42e86 2016-02-23        kinaba: 			int q = uqi.second;
5cb1f42e86 2016-02-23        kinaba: 			if(LastQ>q || (u==LastU && q!=LastQ))
5cb1f42e86 2016-02-23        kinaba: 				return false;
5cb1f42e86 2016-02-23        kinaba: 
5cb1f42e86 2016-02-23        kinaba: 			int Do = (u-LastU)/2 + ((u-LastU)%2==1 && u%2==1 ? 1 : 0);
5cb1f42e86 2016-02-23        kinaba: 			int De = (u-LastU)/2 + ((u-LastU)%2==1 && u%2==0 ? 1 : 0);
5cb1f42e86 2016-02-23        kinaba: 			int Dq = q - LastQ;
5cb1f42e86 2016-02-23        kinaba: 			if(Dq > Do+De)
5cb1f42e86 2016-02-23        kinaba: 				return false;
5cb1f42e86 2016-02-23        kinaba: 
5cb1f42e86 2016-02-23        kinaba: 			LastU=u, LastQ=q;
5cb1f42e86 2016-02-23        kinaba: 			if(Dq == 0)
5cb1f42e86 2016-02-23        kinaba: 				continue;
5cb1f42e86 2016-02-23        kinaba: 
5cb1f42e86 2016-02-23        kinaba: 			set<pair<int,int>> neo;
5cb1f42e86 2016-02-23        kinaba: 			for(auto c: Cand) {
5cb1f42e86 2016-02-23        kinaba: 				int o = c.first;
5cb1f42e86 2016-02-23        kinaba: 				int e = c.second;
5cb1f42e86 2016-02-23        kinaba: 
5cb1f42e86 2016-02-23        kinaba: 				for(int oo=0; oo<=Do && oo<=Dq; ++oo) {
5cb1f42e86 2016-02-23        kinaba: 					int ee = Dq - oo;
5cb1f42e86 2016-02-23        kinaba: 					if(0<=ee && ee<=De && o+oo<=n/2 && e+ee<=n/2) {
5cb1f42e86 2016-02-23        kinaba: 						neo.emplace(o+oo, e+ee);
5cb1f42e86 2016-02-23        kinaba: 					}
5cb1f42e86 2016-02-23        kinaba: 				}
5cb1f42e86 2016-02-23        kinaba: 			}
5cb1f42e86 2016-02-23        kinaba: 			Cand = std::move(neo);
5cb1f42e86 2016-02-23        kinaba: 		}
5cb1f42e86 2016-02-23        kinaba: 
5cb1f42e86 2016-02-23        kinaba: 		return Cand.count(make_pair(n/2, n/2)) > 0;
5cb1f42e86 2016-02-23        kinaba: 	}
5cb1f42e86 2016-02-23        kinaba: };
5cb1f42e86 2016-02-23        kinaba: 
5cb1f42e86 2016-02-23        kinaba: // BEGIN CUT HERE
5cb1f42e86 2016-02-23        kinaba: #include <ctime>
5cb1f42e86 2016-02-23        kinaba: double start_time; string timer()
5cb1f42e86 2016-02-23        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
5cb1f42e86 2016-02-23        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
5cb1f42e86 2016-02-23        kinaba:  { os << "{ ";
5cb1f42e86 2016-02-23        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
5cb1f42e86 2016-02-23        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
5cb1f42e86 2016-02-23        kinaba: void verify_case(const string& Expected, const string& Received) {
5cb1f42e86 2016-02-23        kinaba:  bool ok = (Expected == Received);
5cb1f42e86 2016-02-23        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
5cb1f42e86 2016-02-23        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
5cb1f42e86 2016-02-23        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
5cb1f42e86 2016-02-23        kinaba: #define END	 verify_case(_, BearFair().isFair(n, b, upTo, quantity));}
5cb1f42e86 2016-02-23        kinaba: int main(){
5cb1f42e86 2016-02-23        kinaba: 
5cb1f42e86 2016-02-23        kinaba: CASE(0)
5cb1f42e86 2016-02-23        kinaba: 	int n = 4;
5cb1f42e86 2016-02-23        kinaba: 	int b = 6;
5cb1f42e86 2016-02-23        kinaba: 	int upTo_[] = {3,6};
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
5cb1f42e86 2016-02-23        kinaba: 	int quantity_[] = {2,4};
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
5cb1f42e86 2016-02-23        kinaba: 	string _ = "fair";
5cb1f42e86 2016-02-23        kinaba: END
5cb1f42e86 2016-02-23        kinaba: CASE(1)
5cb1f42e86 2016-02-23        kinaba: 	int n = 4;
5cb1f42e86 2016-02-23        kinaba: 	int b = 6;
5cb1f42e86 2016-02-23        kinaba: 	int upTo_[] = {3,6};
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
5cb1f42e86 2016-02-23        kinaba: 	int quantity_[] = {2,3};
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
5cb1f42e86 2016-02-23        kinaba: 	string _ = "unfair";
5cb1f42e86 2016-02-23        kinaba: END
5cb1f42e86 2016-02-23        kinaba: CASE(2)
5cb1f42e86 2016-02-23        kinaba: 	int n = 2;
5cb1f42e86 2016-02-23        kinaba: 	int b = 6;
5cb1f42e86 2016-02-23        kinaba: 	int upTo_[] = {1,2,3};
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
5cb1f42e86 2016-02-23        kinaba: 	int quantity_[] = {1,1,2};
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
5cb1f42e86 2016-02-23        kinaba: 	string _ = "unfair";
5cb1f42e86 2016-02-23        kinaba: END
5cb1f42e86 2016-02-23        kinaba: CASE(3)
5cb1f42e86 2016-02-23        kinaba: 	int n = 50;
5cb1f42e86 2016-02-23        kinaba: 	int b = 1000;
5cb1f42e86 2016-02-23        kinaba: 	int upTo_[] = {736,205,264,235,273,40,901,37,900,424,122,517,820,402,669,279,455,921,774,923,107,936,484,171,248,
5cb1f42e86 2016-02-23        kinaba: 186,970,231,321,902,606,24,451,585,823,270,361,292,128,521,689,683,270,726,980,652,996,909,196,357};
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
5cb1f42e86 2016-02-23        kinaba: 	int quantity_[] = {35,9,9,9,9,3,46,3,46,18,7,25,39,18,32,9,20,49,37,49,7,49,24,8,9,8,49,9,12,46,29,2,20,29,39,9,16,11,7,27,33,32,9,34,49,32,50,47,8,16};
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
5cb1f42e86 2016-02-23        kinaba: 	string _ = "fair";
5cb1f42e86 2016-02-23        kinaba: END
5cb1f42e86 2016-02-23        kinaba: CASE(4)
5cb1f42e86 2016-02-23        kinaba: 	int n = 4;
5cb1f42e86 2016-02-23        kinaba: 	int b = 1000;
5cb1f42e86 2016-02-23        kinaba: 	int upTo_[] = {400,600};
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
5cb1f42e86 2016-02-23        kinaba: 	int quantity_[] = {4,0};
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
5cb1f42e86 2016-02-23        kinaba: 	string _ = "unfair";
5cb1f42e86 2016-02-23        kinaba: END
5cb1f42e86 2016-02-23        kinaba: /*
5cb1f42e86 2016-02-23        kinaba: CASE(5)
5cb1f42e86 2016-02-23        kinaba: 	int n = ;
5cb1f42e86 2016-02-23        kinaba: 	int b = ;
5cb1f42e86 2016-02-23        kinaba: 	int upTo_[] = ;
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
5cb1f42e86 2016-02-23        kinaba: 	int quantity_[] = ;
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
5cb1f42e86 2016-02-23        kinaba: 	string _ = ;
5cb1f42e86 2016-02-23        kinaba: END
5cb1f42e86 2016-02-23        kinaba: CASE(6)
5cb1f42e86 2016-02-23        kinaba: 	int n = ;
5cb1f42e86 2016-02-23        kinaba: 	int b = ;
5cb1f42e86 2016-02-23        kinaba: 	int upTo_[] = ;
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> upTo(upTo_, upTo_+sizeof(upTo_)/sizeof(*upTo_));
5cb1f42e86 2016-02-23        kinaba: 	int quantity_[] = ;
5cb1f42e86 2016-02-23        kinaba: 	  vector <int> quantity(quantity_, quantity_+sizeof(quantity_)/sizeof(*quantity_));
5cb1f42e86 2016-02-23        kinaba: 	string _ = ;
5cb1f42e86 2016-02-23        kinaba: END
5cb1f42e86 2016-02-23        kinaba: */
5cb1f42e86 2016-02-23        kinaba: }
5cb1f42e86 2016-02-23        kinaba: // END CUT HERE