Rút tiền ATM

Đề bài:
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.

Đầu vào: T số lượng test.
T dòng tiếp theo chứa 2 số W và C

Đầu ra: 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

Bạn chưa đăng nhập? Đăng nhập để Submit ngay!