Hướng dẫn giải của 34 đồng xu


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.