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()
投稿日時:
最終更新: