yukicoder No.2410 Nine Numbers

平衡三進法！

• 問題へのリンク

問題概要

次の条件を満たすサイズ 9 の整数列 を求めよ。

• である
• 以上 以下の任意の整数 に対して、次の操作を繰り返す操作列が存在して、整数列中に整数 が存在する状態にできる
  • 操作 1：数列から 2 つの要素 を選び、その 2 つの整数を削除して、末尾に を挿入する
  • 操作 2：数列から 2 つの要素 を選び、その 2 つの整数を削除して、末尾に を挿入する

解法

つまり、 に対して、 のいずれかを掛けて足した値が連続する整数を表せるようにしたいということ。

となると、平衡三進法しかない！！　次のことがよく知られている。

---

について、 のいずれかを掛けて足すことで、 以上 以下の整数をすべて表すことができる

---

よって、今回の問題についても、 を出力すればよい。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long res = 1;
    for (int i = 0; i < 9; ++i) {
        cout << res << " ";
        res *= 3;
    }
    cout << endl;
}