Tiền xu - LCOJ: Luyện Code Online Judge

ODDCOIN - Tiền xu

Điểm: 3,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

Nước ODD có các đồng xu mệnh giá sau ~1, 3, 5, 10, 30, 50, 100, 300, 500, 1000, 3000, 5000, 10 000, 30 000\text{ và }50 000~ đồng. Ngân hàng ban hành thêm một loại xu mới với mệnh giá ~x~ đồng. Để trả đúng ~t~ đồng, cần tối thiểu bao nhiêu đồng xu?

Input

Dòng đầu ghi số test ~q\le 50~
~q~ dòng sau mỗi dòng ghi hai số ~x, t\ (x\ne t)~

Giới hạn:

~25\%~ số test có ~x ≤ 20, t ≤ 20~
~25\%~ số test khác có ~x ≤ 10^5, t ≤ 10^5~
~25\%~ số test khác có ~x ≤ 5.10^7, t ≤ 5.10^7~
~25\%~ số test còn lại có ~x ≤ 2.10^9, t ≤ 2.10^9~

Output

In ra ~q~ dòng, mỗi dòng là kết quả một test

Sample

Input #1

Output #1

Problem source: PreVNOI Ⅸ (BẮC GIANG 2019)

Bình luận

Please read the guidelines before commenting.

include <bits/stdc++.h>

using namespace std; using ll = long long;

vector<ll> base = {50000,30000,10000,5000,3000,1000,500,300,100,50,30,10,5,3,1};

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

int q; cin >> q;
while (q--) {
    ll x, t;
    cin >> x >> t;
    ll ans = LLONG_MAX;

    // thử dùng k xu mới, với k từ 0 tới ... (đặt giới hạn)
    for (ll k = 0; k*x <= t && k <= 100000; k++) {
        ll rem = t - k*x;
        ll cnt = k;
        // dùng greedy với bộ base
        for (ll v : base) {
            cnt += rem / v;
            rem %= v;
        }
        if (rem == 0) ans = min(ans, cnt);
        // Nếu x rất nhỏ, số k thử nhiều — break nếu cnt > ans để prune
        if (k > ans) break;
    }

    cout << ans << "\n";
}
return 0;

}

đây là hệ tiền chuẩn(3 số cách nhau hệ số 10) có thể dùng tham lam để tính, trường hợp có x duyệt cận w và q - w. bài này có vẻ như ổn nên duyệt full luôn

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, x, q;
set< ll, greater<ll>> a = {50000, 30000, 10000, 5000, 3000, 1000, 500, 300, 100, 50, 30, 10, 5, 3, 1};

ll f(ll n) {
    ll cnt = 0;
    for (ll x : a) {
        cnt += n / x;
        n %= x;
    }
    return cnt;
} 


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); 
    cin >> q;
    while (q--) {
        cin >> x >> t;
        ll maxq = t / x;
        ll ans = f(t);
        for (ll k = 0; k <= maxq; k++) ans = min<ll>(ans, k + f(t - k * x));
        cout << ans << "\n";
    }
}