結果
問題 | No.2420 Simple Problem |
ユーザー |
|
提出日時 | 2023-08-12 14:12:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 716 ms / 2,000 ms |
コード長 | 1,294 bytes |
コンパイル時間 | 356 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 82,432 KB |
最終ジャッジ日時 | 2024-11-19 17:52:28 |
合計ジャッジ時間 | 21,187 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
import sysinput = lambda: sys.stdin.readline().rstrip()def naive(A, B):ng = -1ok = (A+B)*2while abs(ng-ok) > 1:mid = (ok+ng)//2if mid*mid-A-B > 0 and 4*A*B < (mid*mid-A-B)**2: # ここ頑張るok = midelse:ng = midreturn okdef isqrt(n):# n <= X^2 なる最小の X を求めるng = 0ok = n*2while abs(ng-ok) > 1:mid = (ok+ng)//2if n <= mid*mid : # ここ頑張るok = midelse:ng = midreturn okdef solve(A, B):# vA + vB < X# A + 2vAB + B < X2# 2vAB < X2 - A - B =: C# 4AB < C2iseq = TrueC = isqrt(4*A*B)iseq &= 4*A*B == C * CX = isqrt(C+A+B)iseq &= C+A+B == X * Xreturn X+iseqdef main():# 入力N = int(input())for _ in range(N):A, B = map(int, input().split())# 計算・出力ans = solve(A, B)print(ans)if __name__ == "__main__":main()from random import randint# for _ in range(10000):# A = randint(1, 10**9)# B = randint(1, 10**9)# ans1 = naive(A, B)# ans2 = solve(A, B)# if ans1 != ans2:# print(A, B)# print(ans1, ans2)# break