ATMW - Rút tiền ATM (ACMVN 10-2014 C)
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

      Vinh làm việc cho một công ty sản xuất máy ATM. Chức năng cơ bản của một máy ATM là rút tiền mặt. Khi một khách hàng muốn rút W đồng, máy ATM sẽ nhả ra N tờ tiền mà có tổng là W đồng. Trong máy ATM thế hệ tiếp theo, Vinh đang xây dựng một thuật toán để tìm được N (số lượng các tờ tiền) là ít nhất.

      Giả sử máy ATM có các tờ tiền có mệnh giá 1000, 2000, 3000, 5000, 1000 x 101, 2000 x 101, 3000 x 101, 5000 x 101,..., 1000 x 10c, 2000 x 10c, 3000 x 10c, 5000 x 10c với c là một số nguyên dương. Số lượng tờ tiền của tất cả các loại mệnh giá là không giới hạn.

      Bạn hãy giúp Vinh viết chương trình thực hiện yêu cầu trên.

Dữ liệu nhập:

- Là hai số nguyên W và c cách nhau một khoảng trắng (1 ≤ W ≤ 1018; 1 ≤ c ≤ 15)

Dữ liệu xuất: 

- Gồm hai số N và S cách nhau một khoảng trắng. Trong đó N là số lượng ít nhất các tờ tiền và S là số cách mà có thể cho ra N tờ tiền đó.

- Nếu không có cách rút tiền, in ra duy nhất 1 số 0.

Ví dụ

  • input
    1000 1
    output
    1 1
  • input
    7000 1
    output
    2 1
Back to Top