結果

問題 No.1936 Rational Approximation
ユーザー pitPpitP
提出日時 2022-05-13 23:20:58
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 863 bytes
コンパイル時間 88 ms
コンパイル使用メモリ 11,068 KB
実行使用メモリ 8,484 KB
最終ジャッジ日時 2023-09-29 09:02:27
合計ジャッジ時間 1,263 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
8,468 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 17 ms
8,300 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
P,Q = map(int,input().split())
ans = 0

def solve(x,y):
    g = math.gcd(x,y)
    if y//g >= Q:
        return -1
    else:
        return (x+y)//g

left = [ ((P+1)/(Q+1) , 0),((P-1)/(Q-1) , 1),((P-1)/Q , 2),(P/(Q+1) , 3)]
ansl = []
ansl.append(solve(P+1,Q+1))
ansl.append(solve(P-1,Q-1))
ansl.append(solve(P-1,Q))
ansl.append(solve(P,Q+1))

left.sort(reverse=True)

for num , idx in left:
    if num >= P/Q:
        continue
    if ansl[idx] == -1:
        continue
    ans += ansl[idx]
    break


right = [ ((P+1)/(Q+1) , 0),((P-1)/(Q-1) , 1),(P/(Q-1) , 2),((P+1)/Q , 3)]
ansr = []
ansr.append(solve(P+1,Q+1))
ansr.append(solve(P-1,Q-1))
ansr.append(solve(P,Q-1))
ansr.append(solve(P+1,Q))

right.sort()

for num , idx in right:
    if num <= P/Q:
        continue
    if ansr[idx] == -1:
        continue
    ans += ansr[idx]
    break

print(ans)
0