ARC050 B 花束

概要

　今　r 本の赤い花とb 本の青い花がある。
　赤い花と青い花は(1,x), (y,1)のどちらかの個数の組みでしか買うことはできない時、最大で何セット買うことができるか?

考察

　２つの操作の共通項を考えると、一回の操作で両方とも少ない方が1減る。

　そこで、解を決めうち、m セット作れるかどうか、という問題に帰着すると、できるだけ多く買おうとすると(x-1),(y-1)をできるだけ取った時になる。

　数式で表すと

m <= (r - m) // (x - 1) + (b - m) // (y - 1)

ならば、mセット買うことができる。

実装

aotamasaki.hatenablog.com

を見ながらめぐるしき二分探索で書きました。

　今回はできるだけ多いmを求めたいので、ok に条件を満たす最小値0 を、ngに条件を満たさない大きな値r+bをおきました。

#!/usr/bin/env python3
r, b = map(int, input().split())
x, y = map(int, input().split())
# 解の決めうち二分探索
# k を作れるかどうかで決めうつ
# 不変量: １つ花束を作ると両方1以上は減る
# 不変量を意識して１変数のみ考慮すればいい状態に持っていくと
# k を固定した時の最適な条件が一意に決まる

ok = 0
ng = r + b


def is_ok(m):
    if r - m >= 0 and b - m >= 0 and m <= (r - m) // (x - 1) + (b - m) // (y - 1):
        return True  # 作れる
    else:
        return False


def meguru_bisect(ng, ok):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok


print(meguru_bisect(ng, ok))