COIN34 - 34 đồng xu
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
using namespace std;
typedef map<int,int> mii;
const int delta=60000;
const int size=(1<<17)+19;
int coin[40];
int fh[delta];
mii sh;
void maximize(int &x,const int &y) {
if (x<y) x=y;
}
void precount(void) {
coin[0]=2;
coin[1]=3;
coin[2]=5;
int i,j,sf,ss,b;
mii::iterator it;
sh.clear();
for (i=0;i<delta;i=i+1) fh[i]=-1;
for (i=3;i<34;i=i+1) coin[i]=coin[i-1]+coin[i-2]+coin[i-3];
for (i=0;i<(1<<17);i=i+1) {
sf=0;ss=0;b=0;
for (j=0;j<17;j=j+1)
if ((i|(1<<j))==i) {
b++;
sf+=coin[j];
ss+=coin[j+17];
}
maximize(fh[sf],b);
it=sh.find(ss);
if (it==sh.end()) sh[ss]=b;
else maximize((*it).second,b);
}
}
int result(const int &x) {
mii::iterator it,itf,itl;
itf=sh.begin();
if ((*itf).first>=x-delta) itf=sh.lower_bound(x-delta);
itl=sh.end();itl--;
if ((*itl).first<=x) itl=sh.end();
else itl=sh.upper_bound(x);
int res=-1;
int v;
//printf("123\n");
for (it=itf;it!=itl;it++) {
v=(*it).first;
//printf("%d\n",x-v);
if (0<=x-v && x-v<delta)
if (fh[x-v]>=0) maximize(res,(*it).second+fh[x-v]);
}
return (res);
}
void answer(void) {
int t,c,x;
scanf("%d",&t);
for (c=1;c<=t;c=c+1) {
scanf("%d",&x);
printf("Case #%d: %d\n",c,result(x));
}
}
int main(void) {
//printf("Start\n");
precount();
answer();
return 0;
}