Editorial for 34 đồng xu
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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; }
Comments