入出力例 3 によると \(1099898\) 番目に小さい良い整数は \(819264512\approx 0.8 \times 10^9\) であるため，\(10^9\) 以下の良い整数はそこまで多くないことが推測できます．従ってそれらをすべて列挙できれば，ソートして \(N\) 番目のものを取得するという方針で解くことができます．

\(10^9\) は良い整数ではないため \(9\) 桁以下の良い整数を全て列挙できればよいです． ちょうど \(k\) 桁の良い整数全体の集合を \(X_k\)，ちょうど \(k\) 桁の \(2\) の冪全体の集合を \(P_k\) とします． 便宜上 \(X_0=\{0\}\) とすると \(k\geq 1\) に対して以下が成り立ちます．

\[X_k=\bigcup_{i=1}^{k}\left\{x\cdot 10^i+p\mid x\in X_{k-i}, p\in P_i\right\}\]

この式を適切に実装することで列挙することができます．

実際に列挙してみると \(10^9\) 以下の良い整数は \(1257874\) 個であり，十分高速に計算できることがわかります．

実装例(Python)

P = [[] for _ in range(10)]
for k in range(1, 10):
    l = (10 ** (k - 1) - 1).bit_length()
    r = (10 ** k - 1).bit_length()
    P[k] = [1 << i for i in range(l, r)]

X = [set() for _ in range(10)]
X[0] = {0}
A = []
for k in range(1, 10):
    for i in range(1, k + 1):
        X[k] |= {x * (10 ** i) + p for x in X[k - i] for p in P[i]}
    A += list(X[k])
A.sort()

N = int(input())
print(A[N - 1])

個数の評価

良い整数の個数を見積もる方法を説明します．

\(k\) 桁以下の良い整数の個数 \(S_k=|X_1|+\cdots+|X_k|\) を評価します．

\(|P_i|\leq \lceil\log_2 10\rceil=4\) であるため，\(k\geq 1\) に対して以下が成り立ちます．

\[\begin{aligned} S_k-S_{k-1} &=|X_k|\\ &=\left|\bigcup_{i=1}^{k}\left\{x\cdot 10^i+p\mid x\in X_{k-i}, p\in P_i\right\}\right|\\ &\leq\sum_{i=1}^{k}\left|\left\{x\cdot 10^i+p\mid x\in X_{k-i}, p\in P_i\right\}\right|\\ &=\sum_{i=1}^{k}|X_{k-i}|\cdot |P_i|\\ &\leq 4(|X_{k-1}|+\cdots+|X_1|+|X_0|)=4(S_{k-1}+1) \end{aligned}\]

これを利用すると

\[S_k+1\leq 5(S_{k-1}+1)\leq \cdots \leq 5^k(S_0+1)=5^k\]

より \(k\) 桁以下の良い整数は高々 \(5^k-1\) 個であることがわかりました．\(5^9-1=1953124\) であり，これは粗い評価であることも考慮すると今回の制約下では全て列挙しても TL に間に合うと推定できます．