COIN34 spoj – 34 Đồng Xu

<b>Dữ liệu</b> 4 1 5 8 9 <b>Kết quả</b> Case #1: -1 Case #2: 2 Case #3: 2 Case #4: -1

const fi='COIN34.inp'; nmax=10000; maxx=367980; type data=longint; var test,n:data; f:text; A:array[0..34] of data; B:array[0..maxx] of byte; res,x:data; function max(a,b:byte):byte; begin if a>b then exit(a); exit(b); end; procedure try1(i,s:data; slxu:byte); begin if i>20 then exit; try1(i+1,s+a[i],slxu+1); b[s+a[i]]:=max(b[s+a[i]],slxu+1); try1(i+1,s,slxu); end; procedure try2(i,s:data; slxu:byte); begin if i>34 then exit; try2(i+1,s+a[i],slxu+1); if (x-(s+a[i])>=0) and (x-(s+a[i])<=maxx)then begin if ((x-(s+a[i])>=0) and (B[x-(s+a[i])]<>0)) or (x-(s+a[i])=0) then res:=max(res,B[x-(s+a[i])]+slxu+1); end; try2(i+1,s,slxu); end; procedure docfile; var i,j:data; begin A[1]:=2; a[2]:=3; a[3]:=5; fillchar(b,sizeof(b),0); for i:=4 to 34 do A[i]:=a[i-1]+a[i-2]+a[i-3]; res:=0; for i:=1 to 20 do res:=res+a[i]; res:=0; try1(1,0,0); assign(f,fi); reset(f); readln(f,test); for i:=1 to test do begin res:=0; readln(f,x); if x<=maxx then res:=B[x] else try2(21,0,0); if res=0 then res:=-1; writeln('Case #',i,': ',res); end; close(f); end; begin docfile; end.

const COIN = 34; maxm = 391230; var n, res : byte; test, i, x : longint; a, t : array[0..coin] of longint; f : array[0..maxm] of byte; count : array[0..coin] of byte; procedure init; var i : byte; 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]; end; procedure duyet1(i : byte); var j : byte; begin for j:= 0 to 1 do begin t[i]:= t[i-1]; count[i]:= count[i-1]; if j=1 then begin inc(t[i], a[i]); inc(count[i]) end; if i < 20 then duyet1(i+1) else if count[i] > f[t[i]] then f[t[i]]:= count[i] end; end; function max(a, b : byte): byte; begin if a > b then max:= a else max:= b end; procedure duyet2(i : byte); var j : byte; begin for j:= 0 to 1 do begin t[i]:= t[i-1]; count[i]:= count[i-1]; if j=1 then begin inc(t[i], a[i]); inc(count[i]); end; if i < coin then duyet2(i+1) else if (x - t[i] >= 0) and (x - t[i] <= maxm) then if ((x - t[i] > 0) and (f[x - t[i]] <> 0)) or (x - t[i] = 0) then res:= max(res, f[x-t[i]] + count[i]) end end; begin init; duyet1(1); readln(test); t[20]:= 0; count[20]:= 0; for i:= 1 to test do begin readln(x); res:= 0; if x <= maxm then res:= max(res, f[x]); duyet2(21); if res=0 then writeln('Case #', i, ': -1') else writeln('Case #', i, ': ', res) end; readln end.