CodeIQ 挑戦の記録 : 「ロング・ロング・ストリング」問題
CodeIQというサイトで問題に挑戦した記録です。
問題文を要約すると下記の通り
- 自然数に対して関数をを10進数で表した時の桁数と定義する。
- 2以上の自然数に対して関数となるの値をと定義する。
そのようなが存在しない時はと定義する。 - 標準入力からが与えられる。
- を出力する。
方針
題意より は次の数式で表す事ができる。
\begin{align}
floor( \log_{10} {n}^{n} ) + 1 =m
\end{align}
これを変形し、
\begin{align}
m-1 \leq \log_{10} {n}^{n} < m
\end{align}
これをについて解けばのコードが書けるが、この数式を解く能力は自分には無いのであっさり諦める。
上式を
\begin{align}
floor( n \log_{10} n)+1=m
\end{align}
と変形しとなるを探索する事にする。
但し、線形探索では、入力の最大に対して1秒の時間制限をクリアする事は出来無い。
そこで、二分探索を自前で実装する事とする。
実装
提出したコードは下記の通り
(実際は下記をワンライナーにしたもの。134byte)
では、
Sponsored Link