Hướng dẫn giải

Có $a$ đồng xu giá trị $n$ và $b$ đồng xu giá trị $1$. Với mỗi bộ dữ liệu $a, b, n, S$, cần kiểm tra có thể lấy đúng số tiền $S$ hay không. Có tối đa $q \le 10^4$ bộ dữ liệu.

Sub 1: Vét cạn số đồng xu giá trị $n$ — ~O(a)~

Gọi $x$ là số đồng xu giá trị $n$ được lấy, với $0 \le x \le a$ và $x \cdot n \le S$. Phần còn lại $S - x \cdot n$ phải lấy được bằng đồng xu $1$, tức $0 \le S - x \cdot n \le b$. Thử mọi $x$, nếu có một $x$ thỏa thì trả lời YES. Đạt 21/21 test, nhưng khi $a$ lớn và không có $x$ phù hợp sớm thì vòng lặp chậm.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        long long a, b, n, S;
        cin >> a >> b >> n >> S;
        // Vét cạn: thử mọi số đồng xu giá trị n đem dùng x (0 <= x <= a).
        // Phần còn lại S - x*n phải được lấy bằng đồng xu 1, cần 0 <= S - x*n <= b.
        bool ok = false;
        for (long long x = 0; x <= a && x * n <= S; x++) {
            if (S - x * n <= b) {
                ok = true;
                break;
            }
        }
        cout << (ok ? "YES" : "NO") << "\n";
    }
    return 0;
}

Sub 2: Lấy càng nhiều đồng xu $n$ càng tốt — ~O(1)~

Lấy càng nhiều đồng xu giá trị $n$ thì phần còn lại càng nhỏ, nên chọn $x = \min(a, \lfloor S/n \rfloor)$. Khi đó phần còn lại là $S - x \cdot n$, và đáp án là YES khi và chỉ khi $S - x \cdot n \le b$.

Lý do: nếu $a \ge \lfloor S/n \rfloor$ thì phần còn lại nhỏ nhất có thể là $S \bmod n$; nếu $a < \lfloor S/n \rfloor$ thì lấy hết $a$ đồng xu $n$ là tốt nhất.

Ví dụ: $a = 1, b = 2, n = 3, S = 4$: $x = 1$, phần còn lại $1 \le 2$ nên YES. Ví dụ $a = 5, b = 2, n = 6, S = 27$: $x = 4$, phần còn lại $3 > 2$ nên NO.

Bẫy cần chú ý: $S / n$ phải là phép chia nguyên, và $x \cdot n$ có thể lên tới $10^{9}$ nên dùng long long cho an toàn.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        long long a, b, n, S;
        cin >> a >> b >> n >> S;
        // Dùng càng nhiều đồng xu giá trị n càng tốt: x = min(a, S / n).
        // Phần còn lại S - x*n phải không vượt quá b (số đồng xu 1 có).
        long long x = min(a, S / n);
        long long rest = S - x * n;
        cout << (rest <= b ? "YES" : "NO") << "\n";
    }
    return 0;
}