\(M\) を三進数表記した際の \(3^k\) の位 \((0\le k\le 10)\) を \(C_k\) \((0\le C_k < 3)\) と表します。この時、 \(\displaystyle M=\sum_{k=0}^{10} C_k3^k\) が成立します。

ここで、 \(A\) を以下のように構成すると条件を満たします：

• \(A=()\) とする。
• \(k=0,1,\ldots,10\) に対し順番に以下の操作を行う：
  • \(A\) の末尾に \(k\) を \(C_k\) 個追加する。

\(M=7\) の場合を考えると、 \(7_{(10)}=21_{(3)}\) なので上の手順で構築すると \(A=(0,1,1)\) となります。 \(3^0+3^1+3^1=7\) なのでこの \(A\) は確かに条件を満たします。

上で構築した \(A\) の長さ \(N\) が \(1\le N\le 20\) を満たしていることは実際に \(1\) 以上 \(10^5\) 以下の整数 \(M\) 全てに対して上の方法で \(A\) を構築し、その長さを確かめることで証明できます。

実装例(Python3)

M = int(input())
A = []
for k in range(11):
    A += [k] * (M % 3)
    M //= 3
print(len(A))
print(*A)

実装例(C++)

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int M;
    cin >> M;
    vector<int> A;
    for (int k = 0; k <= 10; k++) {
        for (int i = 0; i < (M % 3); i++) {
            A.push_back(k);
        }
        M /= 3;
    }
    cout << A.size() << endl;
    for (int i = 0; i < A.size(); i++) {
        cout << A[i] << " \n"[i == A.size() - 1];
    }
    return 0;
}