d080: P-6-19. 階梯數字 (APCS201802) (@@)
Tags : DP
Accepted rate : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-23 21:33

Content

一個正整數如果從高位數往低位數看過去,每一位數字只會相等或變大,則我們稱它

為階梯數字,例如:9、234、777、11222233。給定一正整數 N,請計算不大於 N

的階梯數字總共有幾個,請注意本題只算正整數,所以 0 不算階梯數字,而且階梯數

字不會以 0 開始。

提示:對於 N 不大的情形,例如 100000,我們可以枚舉每一個不超過 N 的數字來判

斷。對於 N 很大的時候,就需要比較快速的方法了。我們知道所有的一位數 1~9 都

是階梯數字,如果要計算 D 位數的階梯數字總數,我們可以依據最高位數字分成 9

類,然後根據(D - 1)位的 9 類階梯數字總數來計算。

Input

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

Output

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

Sample Input
// 1
25
// 2
101
Sample Output
// 1
22
// 2
54
測資資訊:
記憶體限制: 64 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 :
Tags:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


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