P151SUMB spoj PTIT – ROUND 1B – Đong gạo

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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 *