Series
Time limit1sMemory limit128 MB
Write all integers from n to m as one digit string, sort the digits descending, and report the k-th digit, or NAV if the string is shorter.
- Level
Medium6 of 10
- Topics
- Math, Implementation, Binary search, Prefix sum
- Solved
- No attempts yet
Problem
Write all the natural numbers from to (inclusive) in a row, without any separators, forming a series of decimal digits.
For example, if and , this series is 9899100101102.
Then sort all the digits in non-increasing order: the greatest digits first, then the next greatest, and so on.
For the example above, the sorted series is 9998211110000.
Given the natural numbers , , and , determine which digit is at the -th position of the sorted series.
Input
Three natural numbers , , and , separated by spaces. (, , , )
Output
Output the digit at the -th position of the sorted series. If the length of the series is less than , output the single word NAV.