Official

B - Ternary Strings Editorial by evima


Instead of strings, let us construct ternary numbers. Here, numbers are already padded with zeros, so being the lexicographically largest is equivalent to being the largest number.

We need \(N\) numbers that begin with \(2\). Thus, it is necessary that \(2 \times 3^{(L-1)} +N-1 \leq t\). Actually, we can achieve \(2 \times 3^{(L-1)} +N-1 = t\).

We begin with \(2 \times 3^{(L-1)},2 \times 3^{(L-1)}+1,\cdots,2 \times 3^{(L-1)}+N-1\). Let us convert each of these numbers as follows:

  • in ternary, replace 0 with 1, 1 with 2, 2 with 0.

This results in numbers that all begin with 0 and are pairwise distinct. Similarly, perform the following conversion, too:

  • in ternary, replace 0 with 2, 1 with 0, 2 with 1.

Now we can print these \(3N\) numbers that satisfy the conditions.

posted:
last update: