Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      maxn=131071;
type ar=array[0..maxn] of longint;
var n,m,max,i,re,t,j:longint;
    f,g,h,e,num:ar;
    a,b:array[0..33] of longint;
    p:array[0..17] of longint;
    d:array[0..59138] of longint;

procedure sort(var f,h:ar;l,r:longint);
var x,y,i,j:longint;
begin
     i:=l; j:=r; x:=f[(i+j) div 2];
     repeat
           while f[i]<x do i:=i+1;
           while f[j]>x do j:=j-1;
           if i<=j then
           begin
                y:=f[i]; f[i]:=f[j]; f[j]:=y;
                y:=h[i]; h[i]:=h[j]; h[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(f,h,i,r);
     if l<j then sort(f,h,l,j);
end;

procedure init;
var i,j,t:longint;
begin
     a[0]:=2; a[1]:=3; a[2]:=5; p[0]:=1;
     for i:=3 to 33 do a[i]:=a[i-1]+a[i-2]+a[i-3];
     for i:=0 to 16 do b[i]:=a[i+17];
     for i:=1 to 17 do p[i]:=p[i-1] shl 1;
     m:=16; max:=p[m+1]-1;
     fillchar(f,sizeof(f),0);
     fillchar(num,sizeof(num),0); e[0]:=0;
     for i:=1 to max do
     begin
          t:=i; j:=0; e[i]:=i;
          while t>0 do
          begin
               if t and 1=1 then
               begin
                    f[i]:=f[i]+a[j];
                    inc(num[i]);
               end;
               inc(j);
               t:=t shr 1;
          end;
     end;
     fillchar(g,sizeof(g),0); h[0]:=0;
     for i:=1 to max do
     begin
          h[i]:=i;
          t:=i; j:=0;
          while t>0 do
          begin
               if t and 1=1 then g[i]:=g[i]+b[j];
               inc(j);
               t:=t shr 1;
          end;
     end;
     sort(f,e,0,max);
     sort(g,h,0,max);
     fillchar(d,sizeof(d),0);
     for i:=0 to max do
         if d[f[i]]=0 then d[f[i]]:=num[e[i]]
         else
         begin
              if d[f[i]]<num[e[i]] then d[f[i]]:=num[e[i]];
         end;
end;

begin
     init;
     assign(input,fi);
     reset(input);
     assign(output,fo);
     rewrite(output);
     readln(t);
     for j:=1 to t do
     begin
          readln(n);
          re:=-1;
          for i:=0 to max do
              if (g[i]<=n) and (n-g[i]<=59138) then
              begin
                   if (d[n-g[i]]>0) then
                   begin
                        if num[h[i]]+d[n-g[i]]>re then re:=num[h[i]]+d[n-g[i]];
                   end;
              end
              else
              begin
                   if g[i]>n then break;
              end;
          writeln('Case #',j,': ',re);
     end;
     close(output);
     close(input);
end.

Code mẫu của happyboy99x

#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;
}

Code mẫu của ladpro98

program coin34;//backtrack
uses    math;
type    e=record
        v,c:longint;
        end;
const   fi='';
var     a:array[1..34] of longint;
        save:array[0..10000000] of byte;
        f:array[1..1 shl 15] of e;
        d:longint;
        n,limit,res,t,tt:longint;
        inp:text;

procedure back1(i,s,c:longint);
begin
        if i=limit then
        begin
                save[s]:=max(save[s],c);
                exit;
        end;
        back1(i+1,s,c);
        back1(i+1,s+a[i],c+1);
end;

procedure back2(i,s,c:longint);
begin
        if i=limit then
        begin
                inc(d);
                f[d].v:=s;
                f[d].c:=c;
                exit;
        end;
        back2(i+1,s,c);
        back2(i+1,s+a[i],c+1);

end;

procedure init;
var     i:longint;
begin
        a[1]:=2;a[2]:=3;a[3]:=5;
        for i:=4 to 34 do
        a[i]:=a[i-1]+a[i-2]+a[i-3];
        limit:=21;
        back1(1,0,0);

        limit:=35;
        back2(21,0,0);
end;

procedure process;
var     i,p,t:longint;
begin
        res:=-1;
        if n<=10000000 then
        if save[n]<>0 then
        res:=save[n];
        for i:=2 to d do
        begin
                t:=n-f[i].v;
                if t=0 then
                res:=max(res,f[i].c)
                else
                if (1<=t) and (t<=10000000) then
                begin
                        p:=save[t];
                        if p<>0 then
                        res:=max(res,p+f[i].c);
                end;
        end;
end;

begin
        init;
        assign(inp,fi);
        reset(inp);
        readln(inp,t);
        for tt:=1 to t do
        begin
                readln(inp,n);
                process;
                writeln('Case #',tt,': ',res);
        end;
end.

Code mẫu của RR

{$R+,Q+}
const
  FINP='';
  FOUT='';
  MAXN=34;
var
  a,sum:array[0..MAXN] of longint;
  n,test,t:longint;
  f1,f2:text;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
function count(u:longint):longint;
var
  i,k:longint;
begin
  if u>sum[34] then exit(-1);
  if u=1 then exit(-1);
  if u=2 then exit(1);
  if u=3 then exit(1);
  if u=4 then exit(-1);
  if u=5 then exit(2);
  for i:=1 to 34 do
    if sum[i]>=u then break;
  k:=count(u-a[i]);
  if k=-1 then exit(-1)
  else exit(k+1);
end;
procedure init;
var
  i:longint;
begin
  a[1]:=2; a[2]:=3; a[3]:=5;
  for i:=4 to 34 do a[i]:=a[i-1]+a[i-2]+a[i-3];
  sum[0]:=0;
  for i:=1 to 34 do sum[i]:=sum[i-1]+a[i];
end;
begin
  init;
  openF;
  read(f1,test);
  for t:=1 to test do
    begin
      read(f1,n);
      writeln(f2,'Case #',t,': ',count(n));
    end;
  closeF;
end.

Code mẫu của hieult

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

Code mẫu của ll931110

program coin34;
const
  input  = '';
  output = '';
  maxk = 250000;
  maxn = 34;
  slot = 19;
  maxt = 1 shl (maxn - slot);
var
  fi,fo: text;
  i,nTest: longint;
  a: array[1..maxn] of longint;
  low: array[0..maxk] of longint;
  list: array[1..maxn] of longint;
  b1,b2: array[0..maxt] of longint;
  nb: longint;
  ss,sw: longint;

procedure openfile;
begin
  assign(fi, input);
    reset(fi);

  assign(fo, output);
    rewrite(fo);
end;

procedure closefile;
begin
  close(fo);
  close(fi);
end;

procedure att(i: longint);
var
  j: longint;
begin
  for j := 0 to 1 do
    begin
      list[i] := j;
      if j = 1 then
        begin
          ss := ss + a[i];
          inc(sw);
        end;

      if i = slot then
        begin
          if low[ss] < sw then low[ss] := sw;
        end
      else att(i + 1);

      if list[i] = 1 then
        begin
          ss := ss - a[i];
          dec(sw);
        end;
    end;
end;

procedure att2(i: longint);
var
  j: longint;
begin
  for j := 0 to 1 do
    begin
      list[i] := j;
      if j = 1 then
        begin
          ss := ss + a[i];
          inc(sw);
        end;

      if i = maxn then
        begin
          inc(nb);
          b1[nb] := ss;
          b2[nb] := sw;
        end
      else att2(i + 1);

      if list[i] = 1 then
        begin
          ss := ss - a[i];
          dec(sw);
        end;
    end;
end;

procedure ext(var x,y: longint);
var
  z: longint;
begin
  z := x;  x := y;  y := z;
end;

procedure swap(i,j: longint);
begin
  ext(b1[i],b1[j]);  ext(b2[i],b2[j]);
end;

procedure sort(l,h: longint);
var
  i,j,p: longint;
begin
  if l >= h then exit;
  i := l;  j := h;  p := b1[random(h - l + 1) + l];

  repeat
    while b1[i] < p do inc(i);
    while b1[j] > p do dec(j);

    if i <= j then
      begin
        if i < j then swap(i,j);
        inc(i);
        dec(j);
      end;
  until i > j;

  sort(l,j);  sort(i,h);
end;

procedure precom;
var
  i: longint;
begin
  fillchar(low, sizeof(low), 0);
  a[1] := 2;  a[2] := 3;  a[3] := 5;

  for i := 4 to maxn do a[i] := a[i - 1] + a[i - 2] + a[i - 3];

  ss := 0;
  sw := 0;
  att(1);

  nb := -1;
  att2(slot + 1);
  sort(0,nb);
end;

procedure solve;
var
  i,x: longint;
  t1,t2: longint;
  k1: longint;
  inf,sup,med: longint;
  res: longint;
begin
  readln(fi, x);
  res := -1;

  inf := 0;
  sup := nb;
  repeat
    med := (inf + sup) div 2;
    if b1[med] <= x then
      begin
        t2 := med;
        inf := med + 1;
      end
    else sup := med - 1;
  until inf > sup;

  inf := 0;
  sup := nb;
  repeat
    med := (inf + sup) div 2;
    if b1[med] >= x - maxk then
      begin
        t1 := med;
        sup := med - 1;
      end
    else inf := med + 1;
  until inf > sup;

  for i := t1 to t2 do
    begin
      k1 := x - b1[i];
      if ((k1 = 0) or (low[k1] <> 0)) and (res < b2[i] + low[k1])
        then res := b2[i] + low[k1];
    end;

  writeln(fo, res);
end;

begin
  openfile;
  precom;

  readln(fi, nTest);
  for i := 1 to nTest do
    begin
      write(fo, 'Case #', i, ': ');
      solve;
    end;

  closefile;
end.

Code mẫu của skyvn97

#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;
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int xu[35], total[35];
int n;
int res;

void collect(int i, int v, int s) {
    if(i==0) {
        if(v==0) res >?= s;
        return;
    }
    if(res >= s + i) return;
    if(v>total[i]) return;
    if(xu[i]<=v) {
        collect( i-1, v-xu[i], s+1);
    }
    collect( i-1, v, s);
}

int main() {
    xu[1] = 2;
    xu[2] = 3;
    xu[3] = 5;
    for(int i=4;i<=34;++i) xu[i] = xu[i-1] + xu[i-2] + xu[i-3];
    for(int i=1;i<=34;++i) total[i] = xu[i] + total[i-1];
    //cout << total[34] << endl;
    //cout << xu[34] << endl;
    int st, t;
    scanf("%d", &st);
    for(t=1;t<=st;++t) {
        scanf("%d", &n);
        res = -1;
        collect( 34, n, 0);
        printf("Case #%d: %d\n", t, res);
    }
    //system("pause");
    return 0;
}