結果

問題 No.2368 I love a square root of 2
ユーザー qwewe
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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()
0