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.

 

7 thoughts on “P151SUMB spoj PTIT – ROUND 1B – Đong gạo

    • bái này xử dụng quay lui bạn ạ 😀 cách xử lí bài này bằng div sẽ cho kq sai ở test “11” nên trong bài này mình nghĩ quay lui đặt cận là ổn nhất. 😀

  1. Cho em hỏi cách này có đúng ko ạ: em sử dụng QHĐ, khởi tạo mảng F>5000; F[n]=0. chạy i từ n-1 về 1: F[i]=min(F[i+5],F[i+3])+1. nếu F[0]>5000 thì in ra -1, ngược lại in ra F[0].

  2. cách này nhanh hơn này mấy bác
    #include
    #include
    using namespace std;

    int main()
    {
    int minx = 9999;
    int s;
    cin >> s;
    for(int i = s/5; i>=0; i–){
    if((s-2*i)/3 < minx){
    minx = (s-2*i)/3;
    }
    }
    cout << minx;
    return 0;
    }

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *