aacord’s memo

abcを中心にpythonで解いた問題のメモ、整理をしています。緑になった。

abc 093 D. Worst Case (python)

最大マッチング問題というらしい。
解説を読んだら理解はしたけど

n= (a*b)**0.5
d = int(n)
if n.is_integer():
    d -= 1
ans = d*2-1

c= int((a*b-1)**0.5)
chk = 2*c-1

が同じものになると思っていたので、間違え続けた。(例えば、(a, b) = 134576397, 134576399))
平方根を math.sprt で求めたが普通に **0.5 でいい気がする。
a や b を使わないといけない組はカウントに含めないので注意。

import math
q = int(input())
for i in range(q):
  a,b = map(int,input().split())
  if a == b:
    print(a*2-2)
    continue
  y = max(a,b)
  z = min(a,b)
  ind = math.sqrt(a*b)
  d = int(ind)
  if ind.is_integer():
    d -= 1
  cnt = 0
  if d*(d+1) < a*b:
    if d >= z:
      cnt = 1
    if d+1 >= y:
      cnt = 2
    print(2*d-cnt)
  else:
    if d >= z:
      cnt = 1
    print(2*d-1-cnt)