Đổi tiền ít đồng nhất

Buổi 21 — DP 1D cổ điển Buổi 69-70 — Mock Tổng hợp Dynamic Programming
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $N$ loại tiền xu với các mệnh giá $C_1, C_2, \dots, C_N$ (mỗi loại có số lượng không giới hạn). Hãy tìm số lượng đồng xu ít nhất cần dùng để tạo thành tổng đúng bằng $S$. Nếu không thể tạo thành tổng $S$, in ra -1.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, S$.
  • Dòng thứ hai chứa $N$ số nguyên $C_1, C_2, \dots, C_N$.
Dữ liệu ra

In ra một số nguyên duy nhất là số đồng xu ít nhất, hoặc -1.

Ví dụ
Input Output
3 11
1 5 7
3
Giới hạn

$1 \le N \le 100$, $1 \le S \le 10^6$, $1 \le C_i \le 10^6$.

Draft saved