Tanka Numbers
Time limit8sMemory limit512 MB
Find the N-th smallest positive integer whose decimal digits use exactly two distinct digit values, for N up to 10^18 across up to 100 datasets.
- Level
Medium7 of 10
- Topics
- Combinatorics, Math, Binary search, Implementation
- Solved
- No attempts yet
Problem
願はくは 花の下にて 春死なむ そのきさらぎの 望月のころ
This is one of the famous tanka attributed to the priest Saigyo. A tanka is a form of waka that has been familiar in Japan since long ago, and most tanka consist of five phrases of 5, 7, 5, 7, 7, for 31 syllables in total.
The number 57577 is made up of just two kinds of digits, 5 and 7. Call a positive integer whose decimal representation consists of exactly two kinds of digits a tanka number. For example, 10, 12, 57577, and 25252 are tanka numbers, but 5, 11, 123, and 20180701 are not.
A positive integer N is given. Find the N-th smallest tanka number.
Input
The input consists of at most 100 datasets. Each dataset is given in the following format.
N
The integer N satisfies 1 ≤ N ≤ 10^18.
The end of the input is indicated by a line consisting of a single zero.
Output
For each dataset, output the N-th smallest tanka number on a single line.