COIN34 - 34 đồng xu
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
#include <iostream>
#include <algorithm>
//#include <conio.h>
#define Max -100
using namespace std;
int xu[40],tong[40],mu2[20],f[60000],the,tien,so,t;
int xuly(int x,int k)
{
if(x<=tong[17])
{
//printf("VKL");
if(x>tong[k])
return Max;
if(x>=xu[18] && k>=18)
return max(f[x],f[x-xu[18]]+1);
else return f[x];
}
while(xu[k]>x) k--;
int KQ=Max;
while(x-xu[k]<=tong[k-1])
{
KQ = max(KQ,xuly(x-xu[k],k-1)+1);
k--;
}
return KQ;
}
int main()
{
xu[1] = 2; xu[2] = 3; xu[3] = 5;
tong[1] = 2; tong[2] = 5; tong [3] = 10;
memset(f,Max,sizeof(f));
for(int i = 4;i<=34;i++)
{
xu[i] = xu[i-1]+xu[i-2]+xu[i-3];
tong[i] = tong[i-1]+xu[i];
}
mu2[0] = 1; for(int i = 1;i<=20;i++) mu2[i] = mu2[i-1]*2;
//printf("%d %d %d\n",tinh,tong[17],tong[34]);
for(int i = 0;i<mu2[17];i++)
{
the = i;
t = 0;
tien = 0;
for(int j = 1;j<=17;j++)
{
if(the%2)
{
t++;
tien+=xu[j];
}
the/=2;
}
f[tien] = max(f[tien],t);
}
int n,x,m;
scanf("%d",&n);
for(int i = 1;i<=n;i++)
{
scanf("%d",&x);
m = xuly(x,34);
if(m<0)
printf("Case #%d: -1\n",i);
else printf("Case #%d: %d\n",i,m);
}
// getch();
}