DIGRT - Digital Root Counter
The digital root of a number x is calculated by summing up all digits x, then adding all digits of the sum and so on, until we are left with only a single digit.
For example, if x = 987654, then its digital root d(x) = 9 + 8 + 7 + 6 + 5 + 4 = 39.
Now we sum up digits of 39. d(39) = 3 + 9 = 12.
Now we sum up digits of 12. d(12) = 1 + 2 = 3.
Thus, d(987654) = 3.
Input
The first line gives the number of test cases T (T <= 100).
Each of the next T test cases gives the value of N (N <= 50,000).
Output
For each test case, print 10 integers, each separated by a space, indicating number of digital roots in the range of 1 to N that are equal to i (1 <= i <= 9). Seperate each test case with a new line.
Example
Input:
2
12
40
Output:
2 2 2 1 1 1 1 1 1
5 5 5 5 4 4 4 4 4
Explanation:
For the first case, there are 2 numbers in the range of 1 to 12 that have digital root equal to 1 (1 and 10), 2 numbers that have digital root equal to 2 (2 and 11) and so on.
hide comments
brahiam:
2011-03-28 21:36:47
using System;
|
|
Andrey Maksimenko:
2010-04-19 10:55:44
Instead of
|
Added by: | .:: Pratik ::. |
Date: | 2010-04-16 |
Time limit: | 1.258s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |