[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Giúp mình giải bài đổi tiền này
Một ngân hàng có N loại tiền mệnh giá A[1],A[2],..A[N] với số tiền không giới hạn cần chi trả cho khách hàng một số tiền M đồng.
Cho biết M,N,A là các số nguyên và N≤100;M≤32000;
Yêu cầu: Tìm cách trả sao cho số lượng tờ là ít nhất.
+ Dữ liệu vào file ″DOITIEN.INP″ có dạng Dòng 1 ghi 2 số N,M
Dòng 2 ghi N số nguyên dương A[1],A[2],..,A[N]
+ Kết quả ra file ″DOITIEN.OUT″ có dạng
Nếu không có cách trả ghi ra file một dòng duy nhất ″No Solution″
Nếu có cách trả dòng một ghi ra số lượng tờ ít nhất phải trả, dòng 2 ghi N số ứng với số tờ
cần trả cho mỗi loại tiền.
Ví dụ:
Một ngân hàng có N loại tiền mệnh giá A[1],A[2],..A[N] với số tiền không giới hạn cần chi trả cho khách hàng một số tiền M đồng.
Cho biết M,N,A là các số nguyên và N≤100;M≤32000;
Yêu cầu: Tìm cách trả sao cho số lượng tờ là ít nhất.
+ Dữ liệu vào file ″DOITIEN.INP″ có dạng Dòng 1 ghi 2 số N,M
Dòng 2 ghi N số nguyên dương A[1],A[2],..,A[N]
+ Kết quả ra file ″DOITIEN.OUT″ có dạng
Nếu không có cách trả ghi ra file một dòng duy nhất ″No Solution″
Nếu có cách trả dòng một ghi ra số lượng tờ ít nhất phải trả, dòng 2 ghi N số ứng với số tờ
cần trả cho mỗi loại tiền.
Ví dụ: