P-6-19. 階梯數字 (APCS201802) (@@)


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 1G

Author:
Problem type

一個正整數如果從高位數往低位數看過去,每一位數字只會相等或變大,則我們稱它為階梯數字,例如:9、234、777、11222233。 給定一正整數 N,請計算不大於 N的階梯數字總共有幾個,請注意本題只算正整數,所以 0 不算階梯數字,而且階梯數字不會以 0 開始。  

輸入格式

輸入一個正數字 N。 N <= 1e18。

輸出格式

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

範例輸入 1

25

範例輸出 1

22

範例輸入 2

101

範例輸出 2

54

提示

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


Comments

There are no comments at the moment.