条件を満たす整数を、小さい方からいくつか列挙してみましょう。

    2
   20
   22
  200
  202
  220
  222
 2000
 2002
 2020
 2022
  ...

実は、条件を満たす整数の中で \(K\) 番目に小さいものは、 \(K\) を \(2\) 進数表現した後に、そこに現れる \(1\) を \(2\) に置き換えたものです。例えば、 \(5=101_{(2)}\) ですが、この \(1\) を \(2\) に置き換えると \(202\) となり、これは確かに条件を満たす整数の中で \(5\) 番目に小さいものです。

この理由は、直感的には以下のように説明できます。

• \(2\) 進数では各桁として考えられる数字が \(0\) または \(1\) の \(2\) 種類だが、同じく条件を満たす整数の各桁として考えられる数字も、 \(0\) または \(2\) の \(2\) 種類しかない。
• \(2\) 進数ではより上の位に \(1\) がある方が大きい値を示すが、同じく条件を満たす整数についてもより上の位に \(2\) がある方が大きい値を示す。

では、どのように答えを出力すれば良いでしょうか? いくつかの方針がありますが、実装例では \(10\) 進法から \(2\) 進法への変換結果を文字列として保持した上で、出力する際に 1 を 2 に変換しています。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;

string convert(long long x){
  string res;
  while(x>0){
    res.push_back('0'+(x%2));
    x/=2;
  }
  reverse(res.begin(),res.end());
  return res;
}

void output(string s){
  for(auto &nx : s){
    if(nx=='1'){cout << '2';}
    else{cout << '0';}
  }
  cout << '\n';
}

int main(){
  long long k;
  cin >> k;
  output(convert(k));
  return 0;
}