Đổi tiền

Points: 0.16 (partial)

Time limit: 0.38s

Memory limit: 512M

Input: stdin

Output: stdout

Problem type

Allowed languages

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

Comments

Comments

Please read the guidelines before commenting.

vominhmanh10 commented on Dec. 31, 2025, 3:00 p.m.

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 commented on Nov. 23, 2025, 2:39 p.m. ← edited →

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

-8

RussVN123 commented on May 29, 2025, 3:01 p.m.

NP-Hard problem ?

This comment is hidden due to too much negative feedback. Show it anyway.

-8

THPTHD_Hieu commented on May 30, 2025, 8:42 a.m.

helo

This comment is hidden due to too much negative feedback. Show it anyway.

-8

RussVN123 commented on May 31, 2025, 4:49 p.m.

gà chiến !

This comment is hidden due to too much negative feedback. Show it anyway.

-8

chitxd commented on May 29, 2025, 1:02 p.m.

bai nay lam kieu gi vay

This comment is hidden due to too much negative feedback. Show it anyway.

-9

THPTHD_Hieu commented on May 29, 2025, 2:24 p.m.

đoán xem

This comment is hidden due to too much negative feedback. Show it anyway.