NUMCOINS - Số lượng xu ít nhất
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: longhoang08

TA là một người rất thích sưu tầm những đồng xu. Hiện tại, TA đã sưu tầm được một số lượng
rất lớn đồng xu của n mệnh giá tiền v1, v2, ..., vn. Tìm số đồng xu nhỏ nhất để TA có thể lấy ra
một số tiền có giá trị bằng S để nộp phạt cho anh Long. Biết rằng số lượng đồng xu mỗi loại của
TA là rất lớn, có thể xem như vô hạn.

Dữ liệu

   - Dòng đầu tiên chứa hai số nguyên dương n là số loại tiền xu TA có và S là số tiền TA cần
lấy ra (1 ≤ n ≤ 100, 1 ≤ S ≤ 100000).

   - Dòng thứ hai chứa n số nguyên a1, a2, ..., ai là các mệnh giá tiền mà TA có (1 ≤ a1 < a2 < a3 < ... < an ≤ 100000).

Kết quả

   - Ghi ra một số nguyên duy nhất là số lượng ít nhất đồng xu TA cần để tổng mệnh giá của
chúng đúng bằng S.

Ví dụ

  • input
    2 7
    2 3
    output
    3

TA sẽ lấy ra 2 đồng xu có mệnh giá 2 và một đồng xu có mệnh giá 3 để có số tiền đúng bằng 7.

Back to Top