C - AtCoder AAC Contest 解説 by toam


\(X\) 個のコンテストを開くことはできるか?という問題は \(X\) に関して単調性があるので二分探索ができます.

\(X\) 個のコンテストを開くためには

  • \(n_A\geq X\)
  • \(n_C\geq X\)
  • 余った A\(n_A-X\) 個),余った C\(n_C-X\) 個),B が合計で \(X\) 個以上(\((n_A-X)+n_B+(n_C-X)\geq X\)

を満たす必要があります.

def solve():
    a, b, c = map(int, input().split())

    def f(m):
        if m > min(a, c):
            return False
        rem = (a - m) + (c - m) + b
        return rem >= m

    ng, ok = 10**10, -1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


for _ in range(int(input())):
    solve()

投稿日時:
最終更新: