Nội dung Bài tập
- Mã:
- COINS
- Tên:
- Đồng xu
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- phucnq
Cho N đồng xu, mỗi đồng xu có một giá trị là 1 số nguyên dương. Giả sử số lượng đồng xu mỗi loại là không giới hạn. Hãy tìm giải pháp tối ưu để có được tổng số tiền X sao cho dùng ít đồng xu nhất.
Input: Từ file COINS.INP
- Dòng 1: 2 số nguyên N, X cách nhau một khoảng trắng (1 <= N <= 100, 1 <= X <= 10^5)
- Dòng 2: N số nguyên phân biệt, mỗi số cách nhau một khoảng trắng là giá trị của mỗi đồng xu (giá trị mỗi số không vượt quá 10^6)
Output: Ra file COINS.OUT một số nguyên là số lượng đồng xu cần thiết. Nếu không có cách nào thì xuất -1.
Ví dụ:
COINS.INP
COINS.OUT
3 11
1 5 7
3
Giải thích: Giải pháp tối ưu là dùng 2 đồng xu giá trị 5 và 1 đồng xu giá trị 1.
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...