日々drdrする人のメモ

今日もdrdr、明日もdrdr

ARC057 - C問題: 2乗根

想定解法メモ。

問題は、入力として {a_1a_2 \ldots a_k}が与えられ、
 {\sqrt{N}}の上 {k}桁が {a_1a_2 \ldots a_k}となるような {N}を求める問題。

問題: C - 2乗根


まず、整数 {C = a_1a_2 \ldots a_k}を考え、 {A = C^2, B = (C+1)^2}を計算する。

 {B}が偶数桁になるように0の左詰めを行った時の桁数を {L}とするとき、
 {t (> 0)}を大きくしながら {\underline{10^{-L+2*t} \times A \le N < 10^{-L+2*t} \times B}} となる最小の整数Nを求める。

境界が変化する、小数点以下が"000000..."となるケースに注意する必要がある。

提出コード: Submission #2107525 - AtCoder Regular Contest 057

A = int(input())
A2 = A**2
B = A + 1
B2 = B**2
 
A0 = str(A2)
B0 = str(B2)
L = len(B0)
assert len(A0) + 1 >= L
if len(A0) < L:
    A0 = "0" + A0
if L % 2:
    A0 = "0" + A0
    B0 = "0" + B0
L = len(A0)
 
ans = int(A0)
for i in range(1, L, 2):
    a = int(A0[:i+1])
    b = int(B0[:i+1])
    # 区間[a, b) に含まれる整数Nを求める
    if int("0"+A0[i+1:]) == 0:
        if int("0"+B0[i+1:]) > 0:
            if a <= b:
                ans = a
                break
        else:
            # b = "~~~~~.000000000"等のケース
            if a < b:
                ans = a
                break
    if a == 0:
        continue
 
    if int("0"+B0[i+1:]) > 0:
        if a+1 <= b:
            ans = a+1
            break
    else:
        # b = "~~~~~.000000000"等のケース
        if a+1 < b:
            ans = a+1
            break
print(ans)

境界の扱いでハマった。