Official

C - Even Digits Editorial by en_translator


This problem is clarified with some steps of rewording. Let us explain the steps.
The problem is briefly explained as follows:

Find the \(N\)-th smallest integer obtained by arranging \(0,2,4,6,8\).

Here, we can divide the digits \(0,2,4,6,8\) by \(2\) to replace them with \(0,1,2,3,4\):

Find the \(N\)-th smallest integer obtained by arranging \(0,1,2,3,4\).

An integer obtained by arranging \(0,1,2,3,4\) can be easily handled using base-\(5\) notation.
The conforming integers are:

\[0, 1, 2, 3, 4, 10, 11, 12, 13, 14, 20, \dots.\]

Regarding them as \(5\)-ary numbers, their decimal representations are

\[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, \dots.\]

That is, when the \(N\)-th integer is interpreted as a base-\(5\) integers, it equals \(N-1\).

Therefore, the problem can be rephrased as follows:

Represent \((N-1)\) base \(5\).

One can represent an integer base \(5\) from the least significant digit to the most. (For this part, we already have past problems like ABC186 C, and you can also find it on Google, so we omit the details.)

By implementing the solution to the rephrased problem, the original problem can be solved. (As we have replaced \(0,2,4,6,8\) with \(0,1,2,3,4\), notice that you need to give \(0,1,2,3,4\) back to \(0,2,4,6,8\).)

  • Sample code (C++)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  long long N;
  cin >> N;
  N--;
  vector<int> a;
  while (N) {
    a.push_back(N % 5);
    N /= 5;
  }
  if (a.empty()) a.push_back(0);
  reverse(begin(a), end(a));
  for (auto& x : a) cout << x * 2;
  cout << endl;
}

posted:
last update: