解説(解説を見た)

まず、 $10^{9}$ 以下の $2$ の冪乗は $30$ 個程度です。
サンプル3を見ると、大体 $N = 1.1 \times 10^5$ で $0.8 \times 10^9$ なのが分かります。

また、 $N$ 番目に小さい良い整数は $10^9$ 以下 ( $10^9$ は良い整数ではないので、実質 $10^9$ 未満) なので、意外と良い整数の数は少ないことが推測できます。

つまり、良い整数を全列挙して、ソートすると良いというわけです。
再帰DFSで全列挙を行うのが一番良いと思います。

n = int(input()) - 1

# 2の冪乗を求める
i = 1
bins = []
while i < 10**9:
    bins.append(str(i))
    i *= 2

# 良い整数を管理(重複を除くためにsetを使用)
candidates = set()

# 良い整数を探索する再帰DFS
def dfs(current_str):
    current_len = len(current_str)

    # 各冪乗で試してみる
    for bi in bins:
        # 9桁を超える場合は、以降も超えるのでループを止める
        if current_len + len(bi) > 9:
            break

        next_str = current_str + bi

        # 枝刈りのため、未探索の良い整数の時だけ追加して再帰を行う
        if next_str not in candidates:
            candidates.add(next_str)
            dfs(next_str)

# 空文字から再帰を始める
dfs("")

# 良い整数を小さい順にソートする
sorted_candidates = sorted(map(int, candidates))

# 答えを出力
print(sorted_candidates[n])

提出コード(Python)
https://atcoder.jp/contests/abc451/submissions/74530841

D. Concat Power of 2

解説(解説を見た)