COIN34 - 34 đồng xu
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<map>
using namespace std;
#define TR(v,i) for(typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int MAX = 2000000000;
long long sum;
map<int, int> map1, map2;
int coin[34];
void maximize(int &a, const int &b) { if(a < b) a = b; }
void backtrack(int begin, int end, long long sum, int c, map<int, int> &m) {
if(sum > MAX) return;
if(begin == end) maximize(m[sum], c);
else {
backtrack(begin+1, end, sum, c, m);
backtrack(begin+1, end, sum+coin[begin], c+1, m);
}
}
int main() {
coin[0] = 2; coin[1] = 3; coin[2] = 5;
for(int i = 3; i < 34; ++i) coin[i] = coin[i-1] + coin[i-2] + coin[i-3];
backtrack(0, 17, 0, 0, map1);
backtrack(17, 34, 0, 0, map2);
int T; scanf("%d", &T);
for(int t = 1; t <= T; ++t) {
int x, res = -1; scanf("%d", &x);
TR(map2, it) if(it->first <= x) {
if(map1.count(x - it->first))
maximize(res, it->second + map1[x - it->first]);
} else break;
printf("Case #%d: %d\n", t, res);
}
return 0;
}