結果

問題 No.1274 楽しい格子点
ユーザー gew1fw
提出日時 2025-06-12 13:40:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,422 bytes
コンパイル時間 224 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 211,708 KB
最終ジャッジ日時 2025-06-12 13:45:07
合計ジャッジ時間 6,840 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 56
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
import math

def main():
    A, B = map(int, input().split())
    d1 = A + B
    d2 = A - B

    if d1 == 0 and d2 == 0:
        print("0.250000000000")
        return

    g = math.gcd(abs(d1), abs(d2)) if d1 != 0 or d2 != 0 else 0

    visited = set()
    heap = []
    initial_s = 2
    heapq.heappush(heap, initial_s)
    visited.add(initial_s)

    total = 0.0
    epsilon = 1e-30  # Threshold to stop further processing

    while heap:
        s = heapq.heappop(heap)

        # Calculate the number of valid points for current s
        if g == 0:
            count = 1 if s == 2 else 0
        else:
            max_t = (s - 1) // g
            count = 0
            for t in range(-max_t, max_t + 1):
                if g * abs(t) >= s:
                    continue
                if (s + g * t) % 2 == 0 and (s - g * t) % 2 == 0:
                    count += 1

        contribution = count / (s ** s)
        total += contribution

        # Generate next possible s values
        for delta in [d1, d2]:
            next_s = s + delta
            if next_s >= 2 and next_s not in visited:
                heapq.heappush(heap, next_s)
                visited.add(next_s)

        # Early termination if contribution is negligible
        if contribution < epsilon:
            break

    # Print with sufficient precision
    print("{0:.12f}".format(total))

if __name__ == "__main__":
    main()
0