第七回 アルゴリズム実技検定 G問題

PAST007G

3冪の和で表すので，3進数の形から考える． 今回は，同じ3冪は使えないので， $$2 * 3^{i} = 3^{i+1} - 3^{i}$$ と書き直せばよい． 繰り上がりの様な計算が起きるので，下の桁から計算を確定させていく．

メモ
この問題は， 平衡3進法という問題らしい．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  vll a;

  while(n){

    a.push_back(n%3);

    n /= 3;

  }

  a.push_back(0);

  // reverse(all(a)); // 不要

  ll pow = 1;

  ll i = 0;

  vll ans;

  while(i < a.size()){

    if(a[i] == 1){

      ans.push_back(pow);

    }else if(a[i] == 2){

      ans.push_back(-pow);

      a[i+1]++;

    }else if(a[i] == 3){

      a[i+1]++;

    }

    pow *= 3;

    i++;

  }

  assert(ans.size() <= 100);

  cout << ans.size() << endl;

  rep(i,ans.size()) cout << ans[i] << " ";

  return 0;

}