Rút tiền ngân hàng

Chọn HSG lớp 12 - Bạc Liêu 2012 - Bài 3
Một điểm giao dịch của ngân hàng X có N loại tiền mệnh giá từ A[1], A[2],
A[3], . . , A[N] (đơn vị ngàn đồng) với số lượng tiền mỗi loại không giới hạn. Một khách hàng cần rút với số tiền là M (ngàn đồng). Hãy cho biết cần bao nhiêu tiền mỗi loại để chi trả sao cho số tờ là ít nhất.
Cho biết: N <= 9; A[i] <= 500; M <= 10000
Dữ liêu vào: Cho trong file INP.TXT gồm 2 dòng:
- Dòng đầu là 2 số N, M;
- Dòng thứ hai ghi N số nguyên dương A[1], A[2], A[3], . . , A[N]
Dữ liêu ra: Ghi vào file OUT.TXT gồm:
- Dòng đầu ghi số lượng tờ phải trả;
- Dòng thứ hai ghi N số nguyên không âm ứng với số tờ cần trả cho mỗi loại tiền. Các số ghi trên cùng một dòng được cách ít nhất một dấu cách.
Ví dụ:
   INP.TXT
      6 98
      1 2 5 10 50 100
   OUT.TXT
      8
      1 1 1 4 1 0

                                                       Lời giải tham khảo