(8 ĐIỂM) MỘT KHÁCH HÀNG CÓ N LOẠI TIỀN MỆNH GIÁ M I VÀ SỐ LƯỢNG CỦA TỪ...

Bài 3: (8 điểm)

Một khách hàng có N loại tiền mệnh giá m i và số lượng của từng mệnh giá s i (i = 1..N)

cần thanh toán tiền cho một cửa hàng kinh doanh. Hãy xác định hộ khách hàng số lượng mỗi

loại để trả K đồng cho cửa hàng đó.

Input: Tập tin văn bản MONEY.INP

+ Dòng đầu tiên: Hai số tự nhiên N, K (2  N  15)

+ Dòng thứ 2: n số tự nhiên m ₁ , m ₂ , ..., m _n

+ Dòng thứ 3: n số tự nhiên s ₁ , s ₂ , ..., s _n

Output: Tập tin văn bản MONEY.OUT, n số tự nhiên c 1 , c 2 , ..., c n thể hiện số lượng tờ

tiền mỗi loại cần trả, c 1 m 1 + c 2 m 2 + ... + c n m n = K. Nếu với số tiền đã có khách hàng

không thực hiện trả được K đồng : ghi số 0.

Ví dụ: MONEY.INP MONEY.OUT

7 186

2 3 5 10 20 50 100

0 2 0 0 4 0 1

4 7 2 3 6 2 4