結果
問題 |
No.2368 I love a square root of 2
|
ユーザー |
![]() |
提出日時 | 2025-05-14 13:10:37 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,613 bytes |
コンパイル時間 | 328 ms |
コンパイル使用メモリ | 82,584 KB |
実行使用メモリ | 62,432 KB |
最終ジャッジ日時 | 2025-05-14 13:12:00 |
合計ジャッジ時間 | 2,676 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 WA * 1 |
ソースコード
import math import sys # Set higher recursion depth for safety if needed, although this code is iterative. # sys.setrecursionlimit(2000) def solve(): # Read input N N = int(sys.stdin.readline()) # Handle the base case N=1. The first element is 0 + sqrt(2)*0 = 0. if N == 1: print(0, 0) return # Precompute sqrt(2) for efficiency sqrt2 = math.sqrt(2) # Function to count the number of pairs (a, b) of non-negative integers # such that a + sqrt(2)*b <= K. def count_le(K): # If K is negative, there are no non-negative a, b satisfying the condition. if K < 0: return 0 # Calculate the maximum possible value for b. # Since a >= 0, we must have sqrt(2)*b <= K, so b <= K / sqrt(2). # Use a small epsilon (1e-12) for floating point comparisons/rounding robustness. # int() truncates towards zero. Adding epsilon helps capture boundary cases correctly. max_b = int(K / sqrt2 + 1e-12) total_count = 0 # Use standard integer for count (Python ints handle arbitrary size) # Iterate through all possible values of b from 0 to max_b. for b in range(max_b + 1): # For a fixed b, we need a >= 0 and a <= K - sqrt(2)*b. # Calculate the upper bound for 'a'. max_a_float = K - sqrt2 * b # If max_a_float is effectively negative (allowing for float inaccuracy), # then there are no non-negative 'a' possible for this 'b'. if max_a_float < -1e-12: continue # Calculate floor(max_a_float). This gives the maximum integer value for 'a'. # Add epsilon for robustness when max_a_float is very close to an integer. floor_max_a = math.floor(max_a_float + 1e-12) # The number of possible non-negative integer values for 'a' is floor_max_a + 1 # (from a=0 to a=floor_max_a). # This count must be non-negative. If floor_max_a < 0, the count is 0. if floor_max_a >= 0: # Calculate number of 'a' values. Since floor_max_a is float, cast to int first. num_a = int(floor_max_a) + 1 total_count += num_a # If floor_max_a < 0, there are no non-negative 'a', so we add 0 to total_count. return total_count # Binary search for the value K = X_N, the N-th smallest element. # Estimate an initial range for K. The number of elements <= K is approx K^2 / (2*sqrt(2)). # So K is approx sqrt(2 * sqrt(2) * N). approx_K = 0.0 if N > 0: # Check N>0 to avoid potential math domain error if N=0 (although problem says N>=1) approx_K = math.sqrt(2 * sqrt2 * N) # Set search bounds [low, high]. low = 0.0 # The upper bound should be safely larger than the expected K. # Using approx_K * 2.0 provides a safety margin. # Also ensure 'high' is at least some minimal positive value for small N. high = max(10.0, approx_K * 2.0) # Perform binary search for a fixed number of iterations. # 150 iterations provide very high precision with doubles, sufficient for this problem. for _ in range(150): mid = (low + high) / 2.0 # Check if the search interval has stopped shrinking due to precision limits. if mid <= low or mid >= high: break # Count elements less than or equal to mid. c = count_le(mid) if c >= N: # If count is >= N, 'mid' could be the N-th element or larger. # The N-th element must be in the interval [low, mid]. high = mid else: # If count is < N, 'mid' is too small. # The N-th element must be in the interval [mid, high]. low = mid # After binary search, 'high' contains the best approximation of the N-th element's value. # Let this value be K_found. K_found = high # Now, find the largest element of the form p + sqrt(2)*q (p, q non-negative integers) # such that p + sqrt(2)*q <= K_found. # This element should be the N-th element X_N = p + sqrt(2)*q. max_val = -1.0 best_p, best_q = 0, 0 # Initialize best pair, default is (0,0) for N=1 case. # Iterate through possible 'b' values. Max b is floor(K_found / sqrt(2)). # Add epsilon for robustness. max_b_final = int(K_found / sqrt2 + 1e-12) # Loop through candidate 'b' values from 0 upwards. for b_cand in range(max_b_final + 1): # Calculate maximum possible float value for 'a'. max_a_float = K_found - sqrt2 * b_cand # If max_a is effectively negative, skip this 'b'. if max_a_float < -1e-12: continue # Find the largest integer 'a' <= max_a_float. a_cand_floor = math.floor(max_a_float + 1e-12) # Ensure 'a' is non-negative. if a_cand_floor < 0: continue # Convert candidate 'a' to integer type. a_cand = int(a_cand_floor) # Calculate the value p + sqrt(2)*q for the current pair (a_cand, b_cand). current_val = float(a_cand) + sqrt2 * float(b_cand) # Check if this value is within the bound K_found (allowing tolerance). if current_val <= K_found + 1e-12: # We want the largest value <= K_found. Update if current_val is larger than max_val found so far. # Use a tolerance in comparison to handle floating point inaccuracies. if current_val > max_val + 1e-12: max_val = current_val best_p = a_cand best_q = b_cand # Handling the case where current_val and max_val are numerically equal (within tolerance): # The problem states p, q are unique for the N-th value. This implies values a+sqrt(2)b # should be distinct enough for float precision to differentiate them. # If they are numerically identical, standard practice is often to take the first one found, # or apply some tie-breaking rule. Here, we stick with the simple update logic: # only update if `current_val` is demonstrably larger than `max_val`. # If they are extremely close, the existing `best_p, best_q` pair remains. # This implicitly assumes the first pair yielding the max value is sufficient. # Output the found integer pair (p, q) print(f"{best_p} {best_q}") # Execute the main function solve()