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();
}

Download