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],

Câu 3 (7 điểm):

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 OUT.TXT

5 98

8

1 1 1 4 1 0

1 2 5 10 50 100