Amusing Numbers
Time limit1sMemory limit128 MB
Given K and M, find the smallest N such that K sits at lexicographic position M among the numbers 1 to N.
- Level
Medium7 of 10
- Topics
- Math, Binary search, Implementation, Trie
- Solved
- No attempts yet
Problem
Consider the integers from 1 to N inclusive. Order them lexicographically (that is, as in a dictionary). For example, for N = 11 the order is:
1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9.
Let denote the position (counting from 1) of the number K in this ordering. For example, .
Given K and M, find the smallest N such that .
Input
A single line with two integers K and M (), separated by a space.
Output
If an N with exists, print the smallest such N. Otherwise, print 0.