数字游戏

发布时间: 2017年11月12日 20:06   最后更新: 2017年11月12日 20:08   时间限制: 1000ms   内存限制: 512M

一天计算机之神随手写下了一个数列。这个数列的第N项是由数字1~N依次拼接所得的数。比如第5项为12345,第11项为1234567891011

现在计算机之神想考考你,这个数列前N项有多少数可以被3整除。

第一行为一个整数T(T<=1000),表示数据组数。
接下来T行每行输入一个整数N(N<=10^9),表示考虑数列前N项。

输出T行,每行一个整数代表前N项里有多少项能被3整除。

复制
1
5
3

有:12、123、12345这三项为3的倍数

注意本题数据范围比较大,有 10^9,所以请设计一个运算次数小于 10^9 级别的程序来完成这道题。

此后的题目也请注意一下程序的运行效率。

可以认为程序1秒能进行10^8次操作。

数学

2017 Fudan ACM-ICPC 程序设计校赛网络赛