02/10/2018, 14:53
P151SUMB spoj PTIT – ROUND 1B – Đong gạo
Nguồn đề bài: http://www.spoj.com/ACMPTIT/problems/P151SUMB/ 1. Đề bài P151SUMB spoj Tuyenlv7 bị mẹ giao cho nhiệm vụ đó là đong gạo để mang lên nhà trọ. Anh được mẹ đưa cho 2 loại bịch, là loại 5 kg và 3 kg. Tuyenlv7 sẽ phải đong đủ số gạo mà mẹ cho vào 2 loại bịch trên. Ví dụ ...
Nguồn đề bài: http://www.spoj.com/ACMPTIT/problems/P151SUMB/
1. Đề bài P151SUMB spoj
Tuyenlv7 bị mẹ giao cho nhiệm vụ đó là đong gạo để mang lên nhà trọ. Anh được mẹ đưa cho 2 loại bịch, là loại 5 kg và 3 kg. Tuyenlv7 sẽ phải đong đủ số gạo mà mẹ cho vào 2 loại bịch trên.
Ví dụ mẹ cho 18 kg thì Tuyenlv7 có thể đong bằng 3 bịch 5kg + 1 bịch 3kg hoặc 6 bịch 3 kg.
Hãy giúp anh ấy đong với số lượng bịch ít nhất có thể, nếu không thể đong được, in ra -1.
Input
Dòng duy nhất chứ số N là số gạo mẹ Tuyenlv7 cho ( 0 < N < 5000).
Output
In ra đáp án của bài toán.
Example
Input:
18
Output:
4
2. Code tham khảo P151SUMB spoj PTIT
const fi=';
x:array[1..2] of byte=(3,5);
type data=longint;
var
f:text;
n,k,res,s,sl:data;
ok:boolean;
function min(a,b:data):data;
begin
if a<b then exit(a); exit(b);
end;
procedure try(i:data);
var j,w:data;
begin
w:=n;
if i>2 then
begin
if n=0 then
begin
res:=min(res,sl);
ok:=true;
end;
end
else
for j:=W div x[i] downto 0 do
begin
inc(sl,j);
n:=n-x[i]*j;
try(i+1);
n:=n+x[i]*j;
dec(sl,j);
end;
end;
begin
assign(f,fi); reset(f);
readln(f,n);
close(f);
sl:=0;
ok:=false;
res:=high(data);
try(1);
if ok then
writeln(res)
else
writeln(-1);
end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | const fi='; x:array[1..2] of byte=(3,5); type data=longint; var f:text; n,k,res,s,sl:data; ok:boolean; function min(a,b:data):data; begin if a<b then exit(a); exit(b); end; procedure try(i:data); var j,w:data; begin w:=n; if i>2 then begin if n=0 then begin res:=min(res,sl); ok:=true; end; end else for j:=W div x[i] downto 0 do begin inc(sl,j); n:=n-x[i]*j; try(i+1); n:=n+x[i]*j; dec(sl,j); end; end; begin assign(f,fi); reset(f); readln(f,n); close(f); sl:=0; ok:=false; res:=high(data); try(1); if ok then writeln(res) else writeln(-1); end. |
