3293. 至尊

单点时限: 2.0 sec

内存限制: 256 MB

中国自古以九五为至尊,cdm 受此启发想要出一道相关的题目。cdm 觉得两个数字一起用题目可能题目就会比较难了,因而 cdm 选取了九为主题出题。

定义至尊数为任意相邻两位的和均为 9 的合法正整数,比如 $18\quad 363$ 为至尊数,而 $233\quad 362$ 不是至尊数。合法正整数不具有前导零。$1$ 至 $9$ 中的数不含有相邻位,此处约定这些数中只有 $9$ 为至尊数。cdm 想要知道长度不超过 $n$ 的正整数中有多少至尊数。

输入格式

有多组输入,每组输入有一行正整数 $n$。

保证对于 $40\%$ 的数据,$n \leq 10^8$。

保证对于 $100\%$ 的数据,$n \leq 10^{10000}$。

输出格式

对于每组输入输出一行结果。

样例

Input
1
3
7
9999999999999997
Output
1
19
55
89999999999999965

123 人解决,158 人已尝试。

167 份提交通过,共有 867 份提交。

3.5 EMB 奖励。

创建: 3 年前.

修改: 2 年,9 月前.

最后提交: 1 周,5 天前.

来源: 2017.7.1 少年宫暑假摸底

题目标签