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

 

6 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].

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 *