Bài 3

Một điểm rút tiền ATM có các loại tiền mệnh giá lần lượt như sau: 10.000 đồng, 20.000 đồng, 50.000 đồng, 100.000 đồng, 200.000 đồng và 500.000 đồng (mỗi loại không quá 1 000 tờ). Một khách hàng cần rút ra một số tiền M đồng (Giả sử rằng sau khi đã kiểm tra đầy đủ các thông số về bảo mật cá nhân). Biết rằng số tiền giới hạn mỗi lần rút tại điểm rút tiền ATM có giá trị thấp nhất là 50.000 đồng. Hãy tìm cách trả sao cho khách hàng nhận được số lượng tờ tiền là ít nhất.

Viết chương trình giải quyết các yêu cầu trên với các điều kiện như sau:

Input (Dữ liệu vào) cho trong tập tin BAI03.INP là: Số tiền cần rút (theo quy định số tiền cần rút có đơn vị tính được làm tròn theo mệnh giá tiền có giá trị thấp nhất là 10.000 đồng).

Output (Dữ liệu xuất) ghi vào tập tin BAI03.OUT gồm:

• Nếu không có cách trả ghi 1 dòng duy nhất có nội dung: KHONG THUC HIEN DUOC.
• Nếu có cách trả thì:
  • Dòng 1: ghi số lượng tờ tiền ít nhất phải trả.
  • Dòng 2: ghi các số ứng với số tờ cần trả cho mỗi loại tiền theo thứ tự: 10.000 đồng, 20.000 đồng, 50.000 đồng, 100.000 đồng, 200.000 đồng và 500.000 đồng.