Kiểm tra có thể chọn kích thước gói để khách mua nhiều hơn mong muốn bằng C++

Mô tả bài toán

Khách mua x ∈ [l,r]. Gói size a. Khách mua floor(x/a) gói, dư = x%a. Nếu dư ≥ a/2 thì mua thêm 1 gói. Tìm a sao cho mọi x trong [l,r] đều mua thêm gói (tức dư ≥ a/2).

Ví dụ

l=3,r=4 → chọn a=5: x=3 dư=3≥2.5, x=4 dư=4≥2.5 → True.

Thuật toán

Điều kiện: với mọi x ∈ [l,r], x%a ≥ a/2. Điều này xảy ra khi a > r và a/2 ≤ l? Code: nếu r/2 ≥ l thì false, else true. Giải thích: chọn a = r+1? Cần a > r và a/2 ≤ l → a ∈ (r, 2l]. Tồn tại khi r < 2l → r/2 < l.

Code C++

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

bool solve(int l, int r) {
    if (r/2 >= l) return false;
    else return true;
}

int main() {
    int l=3,r=4;
    cout << solve(l,r) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: 3,4

Output: 1 (true)