AtCoder Regular Contest 050 B - 花束

問題

arc050.contest.atcoder.jp

解法

二分探索で解けます。

ok(med) = (med 個の花束を用意することが出来るか？) というのを判定したいです。

満たさなければならない制約条件は, (それぞれの花束を作る数を a, b として)

x*a + 1*b <= R
1*a + y*b <= B

です。med = a+b を考慮すると,

med + (x-1)*a <= R
med + (y-1)*b <= B

です。この不等式から, a, b の上界が決まりますが, 同時に a+b >= med でなければなりません。すなわち, med <= (R-med)/(x-1) + (B-med)/(y-1) であれば良いです。

ll R, B;
ll x, y;

bool ok(ll med) {
    if (med > R) return false;
    if (med > B) return false;
    ll a = (R-med)/(x-1), b = (B-med)/(y-1);
    return a+b >= med;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> R >> B;
    cin >> x >> y;
    ll low = 0, high = (1ll<<60);
    while (high-low > 1) {
        const ll med = (high+low)/2;
        if (ok(med)) low = med;
        else high = med;
    }
    cout << low << endl;
    return 0;
}