Many thanks to Clive Fraser for creating this problem!
Of the 10 digits that are used to represent numbers in base 10, the three largest are 7, 8 and 9.
Let us define Big Numbers as those positive integers which do not contain any of the digits 0, 1, 2, 3, 4, 5 or 6.
Also, since 8 is larger than 7 a Big Number should not contain more 7s than 8s. Similarly, since 9 is
larger than 8, a Big Number should not contain more 8s than 9s. These conditions together form a complete
definition of Big Numbers.
For example, 9, 99, 89, 989, 978 and 8799 are all Big Numbers. 8, 87, 997, 99877 and 9999888776 are not.
The number 8 contains more 8s than 9s. The number 87 contains more 8s than 9s. The number 997 contains more
7s than 8s. The number 99877 contains more 7s than 8s. The number 9999888776 contains the
disallowed digit 6.
Consider a list of all the positive integers (in order) from which all of the numbers which are not Big Numbers have been removed. The start of this list is:
9, 89, 98, 99, 789, 798, 879, 897, 899, 978, 987, 989, 998, 999, 7899, 7989, 7998, 8799, 8899, 8979, ...
The number in position 1 is 9. The number in position 14 is 999. You will be given a number of positions
in the ordered list and are to find the Big Numbers which are located at these positions.
The first line of the problem will be a single integer N denoting the number of test cases. Each test case will consist of a single integer representing a
position in the sequence of Big Numbers. For each test case you must find the Big Number which appears at the given position. Give these answers, separated by
spaces, as a single string.
Example:
input:
5
14
23
269
43548
3655865
answer:
999 8998 989889 89997878899 899999797989788