COIN - Đổi tiền
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

Giả sử ta muốn đổi số tiền N đồng, và có một nguồn cung cấp vô hạn của các loại tiền với các mệnh giá S = {S1, S2, .., Sm}. Hỏi có bao nhiêu cách đổi? Thứ tự của các đồng tiền không quan trọng.

Dữ liệu vào:

- Dòng đầu chứa hai số nguyên dương N (0 ≤ N ≤ 50) M (0 ≤ M ≤ 250), tương ứng là số tiền và số loại tiền.

- Dòng sau chứa M số nguyên dương, mô tả các mệnh giá tiền.

Kết quả ra: In ra số cách đổi tiền.

Ví dụ

  • input
    4 3
    1 2 3
    output
    4
  • input
    10 4
    2 5 3 6
    output
    5
Back to Top