SMARTATM - Máy rút tiền thông minh
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Ở cổng trường THPT Chuyên Sơn La mới được lắp mới một máy rút tiền tự động. Trong máy có ~n~ loại tiền mệnh giá lần lượt là ~a_1, a_2, …, a_n~, mỗi mệnh giá có số lượng đủ nhiều.
Khi khách hàng có yêu cầu rút số tiền ~M~, chương trình điều khiển sẽ xác định xem có thể trả được số tiền đúng bằng ~M~ không, nếu có, chương trình điều khiển sẽ chọn cách trả với số lượng tờ ít nhất.
Yêu cầu: Hãy tính số lượng tờ tiền ít nhất để trả số tiền ~M~.
Input
- Dòng đầu chứa hai số nguyên dương ~n~ và ~M~;
- Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, …, a_n~ được sắp xếp theo thứ tự tăng dần.
Giới hạn:
- ~1 ≤ n ≤ 20; 1 ≤ a_i ≤ 10^4; 1 ≤ M ≤ 10^5~
Output
- Ghi ra một dòng duy nhất chứa số nguyên dương là số lượng tờ tiền ít nhất nếu có phương án trả, ngược lại ghi ra ~-1~.
Sample
Input #1
3 130
10 60 100
Output #1
3
Hint
Xét #1:Trả hai tờ ~60~ và một tờ ~10~
Problem source: Chuyên Sơn La Online Judge
Bình luận
bài này phải dùng qhd nhá ae link tham khảo: https://www.geeksforgeeks.org/find-minimum-number-of-coins-that-make-a-change/?ref=lbp
nó vẫn như bth thôi man, man làm sai rồi, không thể cứ lấy tờ tiền rồi thêm tờ nhỏ hơn được , ví dụ cần 220 từ 10 60 100, thì code của bạn sẽ là 2 tờ 100 và 2 tờ 10, nhưng đáp án của nó là 2 tờ 60 1 tờ 100
ok tks bro nheee :>