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.
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