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.

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);
for j:=1 to t do
begin
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;
}


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);
for tt:=1 to t do
begin
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;
for t:=1 to test do
begin
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
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;

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