giaoxu03
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bạn được cho một tập hợp các mệnh giá tiền. Tập hợp luôn chứa phần tử mang gía trị 1. Mỗi mệnh giá có vô hạn các đồng tiền mang mệnh giá đó. Cho số tiền \(S\), hãy tìm cách đổi \(S\) thành ít đồng tiền nhất, sao cho mỗi đồng tiền có mệnh giá thuộc vào tập hợp đã cho.
Input
- Dòng 1: Hai số nguyên dương \(N\) (số phần tử của tập hợp mệnh giá tiền) và \(S\) (số tiền cần đổi) (\(1 \leq N \leq 100; 1 \leq S \leq 10^9\)).
- Dòng 2: \(N\) số nguyên dương biểu thị mệnh giá của các phần tử trong tập hợp (giá trị không vượt quá 100).
Output
- Dữ liệu ra gồm một số nguyên duy nhất là số đồng tiền ít nhất có thể đổi được.
Example
Test 1
Input
2 3
1 2Output
2
Bình luận
hmm, dù mình AC rồi nhưng mình vẫn thấy có sơ hở trong cách quy hoạch động. Ví dụ :
3 999999998
1 499999999 999999990
Minh quy hoạch động ra 9 nhưng thực tế 2 là đủ, có cao nhân nào có thể cho mình cách giải hợp lí nhất không ạ
-
0
letangphuquy
8:23 p.m. 10 Tháng 6, 2022
1 bình luận nữamệnh giá tiền thấp thì làm được chứ mệnh giá lớn thì hơi bị khoai