#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 MoneyGame
{
public:
int V1, V2, V3;
map<int, int> memo;
int play(vector <int> lennysCoins, vector <int> fredsCoins, vector <int> values)
{
V1 = values[0];
V2 = values[1];
V3 = values[2];
memo.clear();
return rec( lennysCoins[0], lennysCoins[1], lennysCoins[2],
fredsCoins[0], fredsCoins[1], fredsCoins[2], 0, 0, 0 );
}
int rec(int L1, int L2, int L3, int F1, int F2, int F3, int B1, int B2, int B3)
{
if( !L1 && !L2 && !L3 )
return -(V1*F1+V2*F2+V3*F3);
int key = (L1<<20)|(L2<<16)|(L3<<12)|(F1<<8)|(F2<<4)|(F3<<0);
if( memo.count(key) )
return memo[key];
int score = -0x7fffffff;
if(L1) {
for(int b1=0; b1<=B1 && V1*b1<V1; ++b1)
for(int b2=0; b2<=B2 && V1*b1+V2*b2<V1; ++b2)
for(int b3=0; b3<=B3 && V1*b1+V2*b2+V3*b3<V1; ++b3)
score = max(score, -rec(F1, F2, F3, L1+b1-1, L2+b2, L3+b3, B1-b1+1, B2-b2, B3-b3));
}
if(L2) {
for(int b1=0; b1<=B1 && V1*b1<V2; ++b1)
for(int b2=0; b2<=B2 && V1*b1+V2*b2<V2; ++b2)
for(int b3=0; b3<=B3 && V1*b1+V2*b2+V3*b3<V2; ++b3)
score = max(score, -rec(F1, F2, F3, L1+b1, L2+b2-1, L3+b3, B1-b1, B2-b2+1, B3-b3));
}
if(L3) {
for(int b1=0; b1<=B1 && V1*b1<V3; ++b1)
for(int b2=0; b2<=B2 && V1*b1+V2*b2<V3; ++b2)
for(int b3=0; b3<=B3 && V1*b1+V2*b2+V3*b3<V3; ++b3)
score = max(score, -rec(F1, F2, F3, L1+b1, L2+b2, L3+b3-1, B1-b1, B2-b2, B3-b3+1));
}
return memo[key] = score;
}
// 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(); if ((Case == -1) || (Case == 5)) test_case_5(); }
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() { 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)); }
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)); }
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)); }
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)); }
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)); }
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)); }
// END CUT HERE
};
// BEGIN CUT HERE
int main() {
MoneyGame().run_test(-1);
}
// END CUT HERE