Máy rút tiền thông minh - LCOJ: Luyện Code Online Judge

SMARTATM - Máy rút tiền thông minh

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Ở cổng trường THPT Chuyên Sơn La mới được lắp mới một máy rút tiền tự động. Trong máy có ~n~ loại tiền mệnh giá lần lượt là ~a_1, a_2, …, a_n~, mỗi mệnh giá có số lượng đủ nhiều.

Khi khách hàng có yêu cầu rút số tiền ~M~, chương trình điều khiển sẽ xác định xem có thể trả được số tiền đúng bằng ~M~ không, nếu có, chương trình điều khiển sẽ chọn cách trả với số lượng tờ ít nhất.

Yêu cầu: Hãy tính số lượng tờ tiền ít nhất để trả số tiền ~M~.

Input

Dòng đầu chứa hai số nguyên dương ~n~ và ~M~;
Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, …, a_n~ được sắp xếp theo thứ tự tăng dần.

Giới hạn:

~1 ≤ n ≤ 20; 1 ≤ a_i ≤ 10^4; 1 ≤ M ≤ 10^5~

Output

Ghi ra một dòng duy nhất chứa số nguyên dương là số lượng tờ tiền ít nhất nếu có phương án trả, ngược lại ghi ra ~-1~.

Sample

Input #1

3 130
10 60 100

Output #1

Hint

Xét #1:Trả hai tờ ~60~ và một tờ ~10~

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

0

bnpdat2012 đã bình luận lúc 12, Tháng 4, 2026, 3:48

các bạn bt làm bài Lock trong phần quy hoạch động dễ không giúp tôi vs

include <iostream>

include <vector>

include <algorithm>

include <cmath>

using namespace std;

// Hằng số cho giá trị vô cùng. Vì M <= 10^5, M + 1 là đủ lớn. const int INF = 1e5 + 1;

void solve() { // Đọc số lượng mệnh giá n và số tiền cần rút M int n, M; if (!(cin >> n >> M)) return;

// Đọc n mệnh giá tiền
vector<int> a(n);
for (int i = 0; i < n; ++i) {
    cin >> a[i];
}

// Khai báo mảng DP
// DP[i] là số tờ tiền ít nhất để có tổng tiền là i
vector<int> dp(M + 1, INF);

// Trường hợp cơ sở: 0 đồng cần 0 tờ tiền
dp[0] = 0;

// Lặp qua tất cả các tổng tiền từ 1 đến M
for (int i = 1; i <= M; ++i) {
    // Lặp qua tất cả các mệnh giá
    for (int coin : a) {
        // Nếu mệnh giá nhỏ hơn hoặc bằng tổng tiền hiện tại
        if (coin <= i) {
            // Áp dụng công thức truy hồi: dp[i] = min(dp[i], dp[i - coin] + 1)
            if (dp[i - coin] != INF) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
}

// Kết quả cuối cùng là dp[M]
int result = dp[M];

// In ra kết quả
if (result == INF) {
    cout << -1 << endl;
} else {
    cout << result << endl;
}

}

int main() { // Tối ưu hóa I/O iosbase::syncwith_stdio(false); cin.tie(NULL);

solve();

return 0;

}

include <bits/stdc++.h>

using namespace std;

int main() { ios::syncwithstdio(false); cin.tie(nullptr);

int n, m;
cin >> n >> m;
vector<int> c(n);
for(int i = 0; i < n; i++) cin >> c[i];

const int INF = 1e9;
vector<int> dp(m+1, INF);
dp[0] = 0;

for(int i = 0; i < n; i++) {
    for(int x = c[i]; x <= m; x++) {
        dp[x] = min(dp[x], dp[x - c[i]] + 1);
    }
}

if(dp[m] == INF) cout << -1;
else cout << dp[m];

return 0;

}

0

MrDat đã bình luận lúc 2, Tháng 6, 2025, 4:22

có bạn nào giải bài này bằng greedy không, mình giải bằng thuật này nhưng bị AC 5 test cuối. Dù sửa rất nhiều nhưng không hiểu sai ở đâu

1

dungolduck đã bình luận lúc 12, Tháng 2, 2024, 2:24

bài này phải dùng qhd nhá ae link tham khảo: https://www.geeksforgeeks.org/find-minimum-number-of-coins-that-make-a-change/?ref=lbp

8

mquan1503 đã bình luận lúc 12, Tháng 1, 2024, 14:00

nó vẫn như bth thôi man, man làm sai rồi, không thể cứ lấy tờ tiền rồi thêm tờ nhỏ hơn được , ví dụ cần 220 từ 10 60 100, thì code của bạn sẽ là 2 tờ 100 và 2 tờ 10, nhưng đáp án của nó là 2 tờ 60 1 tờ 100