ABC077-B - Around Square を解く(2)

ABC077-B - Around Square を解く(1) の続き

1から順に列挙していく方法ではTLEになってしまった

試しに手元で実行して 10^9 を入力してみたら5分経っても終わる気配がなかった

提出する前に気づけましたねこれは…

ということで、もっと効率のよい方法を考える必要がある

例えば、平方根を使う方法

もし入力値が 10000 であれば、その平方根である 100 を

2乗したもの（ = 10000 ）が答えなので

一発で解答を求めることができる

では、9999 の場合はどうなるか？ 

>>> import math
>>> math.sqrt(9999)
99.99499987499375

平方根は 100 よりは少し小さい値になるようだ

それでは、10001 の場合は？

>>> math.sqrt(10001)
100.00499987500625

 

平方根は 100 より少し大きい値となった

 

ここで、問題の内容をよく確認してみると

9999 の場合は 99 × 99 ( = 9801 ) が答えになるべきであり

10001 の場合は 100 × 100 ( = 10000 ) が答えになるべきである

つまり

平方根を求めて、小数点以下を切り捨てたもの2乗すればいいことがわかる

以上を踏まえて書いたコードを以下に示す

 

提出したコード

import math

# 入力
N=int(input())

print(int(math.sqrt(N))*int(math.sqrt(N)))

 

提出結果はACでした