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