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 <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: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class MoneyGame 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: public: 4fd800b3a8 2011-02-23 kinaba: int V1, V2, V3; 4fd800b3a8 2011-02-23 kinaba: map<int, int> memo; 4fd800b3a8 2011-02-23 kinaba: int play(vector <int> lennysCoins, vector <int> fredsCoins, vector <int> values) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: V1 = values[0]; 4fd800b3a8 2011-02-23 kinaba: V2 = values[1]; 4fd800b3a8 2011-02-23 kinaba: V3 = values[2]; 4fd800b3a8 2011-02-23 kinaba: memo.clear(); 4fd800b3a8 2011-02-23 kinaba: return rec( lennysCoins[0], lennysCoins[1], lennysCoins[2], 4fd800b3a8 2011-02-23 kinaba: fredsCoins[0], fredsCoins[1], fredsCoins[2], 0, 0, 0 ); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int rec(int L1, int L2, int L3, int F1, int F2, int F3, int B1, int B2, int B3) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( !L1 && !L2 && !L3 ) 4fd800b3a8 2011-02-23 kinaba: return -(V1*F1+V2*F2+V3*F3); 4fd800b3a8 2011-02-23 kinaba: int key = (L1<<20)|(L2<<16)|(L3<<12)|(F1<<8)|(F2<<4)|(F3<<0); 4fd800b3a8 2011-02-23 kinaba: if( memo.count(key) ) 4fd800b3a8 2011-02-23 kinaba: return memo[key]; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int score = -0x7fffffff; 4fd800b3a8 2011-02-23 kinaba: if(L1) { 4fd800b3a8 2011-02-23 kinaba: for(int b1=0; b1<=B1 && V1*b1<V1; ++b1) 4fd800b3a8 2011-02-23 kinaba: for(int b2=0; b2<=B2 && V1*b1+V2*b2<V1; ++b2) 4fd800b3a8 2011-02-23 kinaba: for(int b3=0; b3<=B3 && V1*b1+V2*b2+V3*b3<V1; ++b3) 4fd800b3a8 2011-02-23 kinaba: score = max(score, -rec(F1, F2, F3, L1+b1-1, L2+b2, L3+b3, B1-b1+1, B2-b2, B3-b3)); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: if(L2) { 4fd800b3a8 2011-02-23 kinaba: for(int b1=0; b1<=B1 && V1*b1<V2; ++b1) 4fd800b3a8 2011-02-23 kinaba: for(int b2=0; b2<=B2 && V1*b1+V2*b2<V2; ++b2) 4fd800b3a8 2011-02-23 kinaba: for(int b3=0; b3<=B3 && V1*b1+V2*b2+V3*b3<V2; ++b3) 4fd800b3a8 2011-02-23 kinaba: score = max(score, -rec(F1, F2, F3, L1+b1, L2+b2-1, L3+b3, B1-b1, B2-b2+1, B3-b3)); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: if(L3) { 4fd800b3a8 2011-02-23 kinaba: for(int b1=0; b1<=B1 && V1*b1<V3; ++b1) 4fd800b3a8 2011-02-23 kinaba: for(int b2=0; b2<=B2 && V1*b1+V2*b2<V3; ++b2) 4fd800b3a8 2011-02-23 kinaba: for(int b3=0; b3<=B3 && V1*b1+V2*b2+V3*b3<V3; ++b3) 4fd800b3a8 2011-02-23 kinaba: score = max(score, -rec(F1, F2, F3, L1+b1, L2+b2, L3+b3-1, B1-b1, B2-b2, B3-b3+1)); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return memo[key] = score; 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: public: 4fd800b3a8 2011-02-23 kinaba: 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(); if ((Case == -1) || (Case == 5)) test_case_5(); } 4fd800b3a8 2011-02-23 kinaba: private: 4fd800b3a8 2011-02-23 kinaba: 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(); } 4fd800b3a8 2011-02-23 kinaba: 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; } } 4fd800b3a8 2011-02-23 kinaba: void test_case_0() { int Arr0[] = {0,1,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {0,1,1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {20,10,2}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = -2; verify_case(0, Arg3, play(Arg0, Arg1, Arg2)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_1() { int Arr0[] = {0,1,2}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {0,1,1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {20,10,2}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 2; verify_case(1, Arg3, play(Arg0, Arg1, Arg2)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_2() { int Arr0[] = {1,1,0}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {0,0,1}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {1,5,10}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 0; verify_case(2, Arg3, play(Arg0, Arg1, Arg2)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_3() { int Arr0[] = {4,4,3}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {4,3,4}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {100,753,100}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 600; verify_case(3, Arg3, play(Arg0, Arg1, Arg2)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_4() { int Arr0[] = {0,0,0}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {5,5,5}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {1000,1000,1000}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = -15000; verify_case(4, Arg3, play(Arg0, Arg1, Arg2)); } 4fd800b3a8 2011-02-23 kinaba: void test_case_5() { int Arr0[] = {3,2,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {0,0,0}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {6,8,14}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 42; verify_case(5, Arg3, play(Arg0, Arg1, Arg2)); } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: int main() { 4fd800b3a8 2011-02-23 kinaba: MoneyGame().run_test(-1); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE