結果
問題 |
No.1274 楽しい格子点
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:33:01 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,422 bytes |
コンパイル時間 | 536 ms |
コンパイル使用メモリ | 82,692 KB |
実行使用メモリ | 122,888 KB |
最終ジャッジ日時 | 2025-06-12 13:39:27 |
合計ジャッジ時間 | 7,794 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 1 |
other | TLE * 1 -- * 56 |
ソースコード
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()