結果
| 問題 |
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 |
ソースコード
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()