結果

問題 No.1936 Rational Approximation
コンテスト
ユーザー pitP
提出日時 2022-05-13 23:20:58
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 863 bytes
コンパイル時間 106 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-07-22 03:38:14
合計ジャッジ時間 1,235 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 13
権限があれば一括ダウンロードができます

ソースコード

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