d088. P_6_19 階梯數字 (APCS201802) (@@)

Content

一個正整數如果從高位數往低位數看過去，每一位數字只會相等或變大，則我們稱它為階梯數字，例如：9、234、777、11222233。

給定一正整數 $N$，請計算不大於 $N$ 的階梯數字總共有幾個，請注意本題只算正整數，所以 $0$ 不算階梯數字，而且階梯數字不會以 $0$ 開始。

Input

輸入一個正數字 $N$。$N \le 8 \times 10^{18}$。

Output

不大於 $N$ 的階梯數字個數。

Sample Input #1

Sample Output #1

Sample Input #2

Sample Output #2

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1K
公開測資點#3 (20%): 1.0s , <1K
公開測資點#4 (20%): 1.0s , <1K

Hint ：

對於 $N$ 不大的情形，例如 100000，我們可以枚舉每一個不超過 $N$ 的數字來判斷。對於 $N$ 很大的時候，就需要比較快速的方法了。我們知道所有的一位數 1~9 都是階梯數字，如果要計算 $D$ 位數的階梯數字總數，我們可以依據最高位數字分成 9 類，然後根據 $(D - 1)$ 位的 9 類階梯數字總數來計算。

Tags:

ch6

出處:

Prof. Wu [管理者：

ktlai (K．我已霸榜．Tlai)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」