$$\newcommand{\Ord}{\mathcal{O}}$$

1443. 遞迴問題

連結:https://tioj.ck.tp.edu.tw/problems/1443

題目大意

$$F(n)=\begin{cases}0&\text{if }n=0\\F([\frac{n}{2}])+n-2[\frac{n}{2}]&\text{otherwise}\end{cases}$$

給定$n$,問$F(0),F(1)\dots, F(n)$中的最大值為何。

題解

如果仔細觀察一下,$F(n)$的結果是$n$寫成二進位時有多少$1$,因此這題要問的答案就很明顯了,就是到數字$n$二進位最多有幾個$1$。答案等於$\lfloor\log_2{(N+1)}\rfloor$。

這裡做法有點懶惰,直接用python大數算,速度跟自己開大數模板差不多。

AC Code

1
2
import math
print(math.floor(math.log(int(input())+1,2)))