SELFNUM - Fashionable self-describing numbers
You decided to start an online dating site for mathematical objects. Every set, number, algebraic structure and lemma can register on your site and start describing its good qualities in its profile.
This is especially easy for numbers which directly describe themselves when you read them. For example, the number 10123133 contains one “0”, one “2”, three “1”s and three “3”s. We call numbers like that self describing numbers, and they are very popular.
A bit more formally, an integer is a self-describing number if we can split it into pairs of ((count, digit), (count, digit), (count, digit), …) where for every (count, digit) pair, our number really contains that digit that many times. All counts must be written without leading zeros and all digits appearing in the number must be specified exactly once.
However, the digit f has fallen out of fashion. Any number that contains the digit f has no chance.
Consider all self-describing numbers that don’t contain the forbidden digit f. Print the n-th smallest such number. (The first n − 1 self describing numbers are out of your league.)
The input contains multiple testcases. Their number 1 ≤ T ≤ 5 is on the first line.
Each testcase is a single line with two integers n and f, where 1 ≤ n ≤ 109 and 0 ≤ f ≤ 9.
Print the n-th smallest self describing number that doesn’t contain the digit f.
The input will be chosen so that the answer always exists.
The number 22 is self describing – we can split it as ((2,2)). It is the smallest self describing number that doesn’t contain the digit 1.
We can read 10143133 as ((1, 0),(1, 4),(3, 1),(3, 3)). This is the smallest self describing number that doesn’t contain the digit 2.
Wow, that was really great analysis heavy problem. Really enjoyed it, thanks Hodobox! Do you have any link to the problem you based this on?