Official

C - 321-like Searcher Editorial by en_translator


An important fact is that any digit does not occur twice or more in a 321-like number.
Thus, it seems that we can perform a search like:

  • does it contain one \(0\), or does not?
  • does it contain one \(1\), or does not?
  • \(\vdots\)
  • does it contain one \(9\), or does not?

Moreover, it appears that we only have to consider the cases where the digits are sorted in descending order.
For example, once we have determined to use \(1,3,7\), and \(8\), then we only have to consider \(8731\) obtained by sorting them in descending order.
Moreover, since a 321-like number is a positive integer, it is forbidden to use nothing, and use only \(0\); for all other \(2^{10}-2 = 1022\) choices, there is a unique corresponding 321-like Number.

First try all of these \(1022\) ways, sort the resulting 321-like numbers in ascending order, and take the \(K\)-th of them, letting it the answer; then the problem is solved.
One can use bit bruteforcing to implement it simply (which is adopted in the sample code), but there are also many other possible approaches.

Note that there is a critical edge case.
All \(9\)-or-less-digit 321-like numbers fit into a \(32\)-bit signed integer type, but \(9876543210\), the answer to \(K=1022\), does not fit into a \(32\)-bit signed integer type. To handle this issue, one has to use an integer type that can store \(9876543210\), or use a conditional branch to handle this case.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  vector<long long> ans;
  for(int i=2;i<(1<<10);i++){
    long long x=0;
    for(int j=9;j>=0;j--){
      if(i&(1<<j)){
        x*=10;
        x+=j;
      }
    }
    ans.push_back(x);
  }
  sort(ans.begin(),ans.end());

  int k;
  cin >> k;
  cout << ans[k-1] << "\n";
  return 0;
}

posted:
last update: