Đổi tiền

Điểm: 0,16 (OI)

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

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

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 giá 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ữ liệu vào gồm ~2~ dòng:

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.

Sample Input

2 3
1 2

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

vominhmanh10 đã bình luận lúc 31, Tháng 12, 2025, 15:00

vì a[i] <= 100, việc S gần đạt 10^9 đồng nghĩa với lời giải tối ưu phải có lượng lớn tờ tiền max a[i]
ta chỉ cần tính lượng lớn tờ tiền đó rồi xét S ở ngưỡng nhỏ hơn(khoảng 10000 - 100000), lúc này ta sẽ quy hoạch động thôi

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define IO ios::sync_with_stdio(0); cin.tie(0)
#define fi first
#define se second
#define pb push_back
#define fast_func inline __attribute__((always_inline))
#define all(v) v.begin(), v.end()
const ll maxn = 1e6 + 5, inf = 1e18, mod = 1e9 + 7;
ll n, S, dp[maxn], dq[maxn];
int main() {
    IO; cin >> n >> S;
    fill(dp, dp + maxn, inf);
    fill(dq, dq + maxn, inf);
    vector<ll> a(n);
    ll maxa = 0;
    for (ll &x: a) {
        cin >> x;
        maxa = max(maxa, x);
    }
    ll res = 0;
    if (S > 10000) {
        res = (S - 10000) / maxa;
        S -= maxa * res;
    }
    dq[0] = 0;
    for (ll x: a) {
        for (ll j = 0; j <= S; ++j) {
            if (j >= x) dp[j] = min(dq[j], dp[j - x] + 1);
            else dp[j] = dq[j];
        }
        swap(dp, dq);
    } 
    cout << dq[S] + res;
}

8

skyvn97 đã bình luận lúc 23, Tháng 11, 2025, 14:39 ← chỉnh sửa →

Lời giải chi tiết: https://youtube.com/shorts/nvnWQJZaSH8

-8

RussVN123 đã bình luận lúc 29, Tháng 5, 2025, 15:01

NP-Hard problem ?

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-8

THPTHD_Hieu đã bình luận lúc 30, Tháng 5, 2025, 8:42

helo

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-8

RussVN123 đã bình luận lúc 31, Tháng 5, 2025, 16:49

gà chiến !

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-8

chitxd đã bình luận lúc 29, Tháng 5, 2025, 13:02

bai nay lam kieu gi vay

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-9

THPTHD_Hieu đã bình luận lúc 29, Tháng 5, 2025, 14:24

đoán xem

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.