(1,0 ĐIỂM) ĐỔI TIỀNMỘT NGÂN HÀNG CÓ N LOẠI TIỀN MỆNH GIÁ A[1],...

Câu 5. (1,0 điểm)

ĐỔI TIỀN

Một ngân hàng có N loại tiền mệnh giá A[1], A[2], ..., A[N] với số lượng tiền mỗi loại

không giới hạn. Cần chi trả cho khách hàng một số tiền M đồng. Hãy cho biết cần bao nhiêu tờ

cho mỗi loại tiền để tổng số tờ là ít nhất.

Dữ liệu vào từ file: TIEN.INP gồm 2 dòng

-

Dòng đầu tiên ghi 2 số N, M (0 < N ≤ 10; 0 < M ≤ 1000)

-

Dòng thứ hai ghi N số: A[1], A[2], ..., A[N] các số cách nhau bởi dấu cách.

Kết quả ghi ra file: TIEN.OUT gồm 2 dòng

-

Dòng đầu tiên ghi số tờ cần dùng, nếu không thể đổi được thì ghi số 0 và không cần

thực hiện tiếp.

-

Dòng tiếp theo ghi n số ( mỗi số biểu hiện cho số tờ cần dùng cho mỗi loại).

Ví dụ

TIEN.INP

TIEN.OUT

5 98

1 5 10 20 50

7

3 1 0 2 1