Responsive image

问题 3421 --数数(Hard)

3421: 数数(Hard)

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 26
[提交][状态][讨论版][命题人:]

题目描述

又有一天，工作室又需要统计人数，现在小劉又开始数人数，还是之前的原因(┐(￣ヘ￣）┌ ･･･)，由于小劉数学极差，因此他数数的时候总是会忘记数数字8，也就是说他数完7以后，就会直接数数字9，直观的讲就是数字n中的每一位都不会出现8，最后小劉数错了人数。现在需要你帮助小劉纠正数数的问题，给出小劉的数数结果n，也就是错误的数数结果n，现在请你帮助他输出正确的数数结果。（本题与Easy唯一的区别就是数据范围）

输入描述

第一行一个数t，表示一共有t组样例(1<=t<=105)
接下来每个样例中
第一行一个数字n，表示小劉的数数结果(1<=n<=1018)
保证数字n中的每一位都不会出现8

输出描述

输出t个纠正小劉数数错误的结果，每个结果占一行

样例输入

2
10
90

样例输出

9
72

提示

对题目中样例的解释：

第一个，小劉数到了10，但是因为小劉数过7之后，就直接开始数9，所以跳过了8，少数了一个数字，就输出9

第二个，小劉数到了90，但是在数到7，17，27，37，47，57，67，77，都会跳过8，18，28，38，48，58，68，78，所以这样会少数8

但是当跳过78后，开始数79，正常会数80，但是小劉会跳过数字8，所以会直接数到90，这样又会少数10

因此总共少数18个数，那么纠正后的数数结果就是72，输出72即可


来源

23软3刘震峰 

[提交][状态]
ACM算法攻关部