答えを先に述べます。答えは次の C++ のコード片で表されるアルゴリズムにより計算できます。

vector<int> ans{K};
for (int n = 0; n < N; n++) {
  vector<int> nxt;
  for (int a : ans) {
    nxt.push_back(a / 2);
    nxt.push_back(a - a / 2);
  }
  ans = nxt;
}

(証明) \(K\) が \(2^N\) で割り切れる場合とそうでない場合で場合分けして考えます。

1. \(K\) が \(2^N\) で割り切れる場合

\(K\) が \(2^N\) で割り切れる場合、 \(B\) を \(\frac{K}{2^N}\) が \(2^N\) 個並んだ数列とすればアンバランスさ \(0\) を達成できて、これが最小です。上記のアルゴリズムが \(\frac{K}{2^N}\) が \(2^N\) 並んだ数列を生成することが確認できるため、問題は起こりません。

2. \(K\) が \(2^N\) で割り切れない場合

\(K\) が \(2^N\) で割り切れない場合、 アンバランスさ \(0\) を達成することはできません。つまり、少なくともアンバランスさは \(1\) 以上です。
逆に、上記のアルゴリズムがアンバランスさ \(1\) を達成することが証明できます。
証明の概要は次の通りです。上記のアルゴリズムでは数列の長さを \(1, 2, \dots, 2^N\) と倍々にしていて、これは問題文中の操作の逆操作になっています。つまり、「操作過程で出てくる数列 ans に含まれる値の最大値と最小値の差」の最大値がアンバランスさになります。

ここで補題として、ans に含まれる値の最大値と最小値の差は常に \(1\) 以下であることが証明できます。
補題の証明方針は次の通りです。ans に含まれる値の最大値と最小値の差が \(1\) 以下である場合は次の 3 通りのいずれかです。また、初期状態は A です。

• A: (最大値) = (最小値) である場合
• B: ある整数 \(m\) を用いて (最大値) \(= 2m+1\), (最小値) \(=2m\) と表せる場合
• C: ある整数 \(m\) を用いて (最大値) \(= 2m\), (最小値) \(=2m-1\) と表せる場合

この時、A,B,C の状態から 1 回操作した後も A,B,C いずれかの状態になることが証明できます。(詳細は省略しますが場合分けにより示せます。なお、 a から a / 2 と a - a / 2 を得る操作は \(a\) から \(\lfloor a/2 \rfloor\) と \(\lceil a/2 \rceil\) を計算する操作である点に注意します。) よって補題が示されました。

以上より、アルゴリズムで得られる数列のアンバランスさは \(1\) であることが証明できたので、これが求めたい答えとなります。

計算量は \(\mathrm{O}(2^N)\) で十分高速です。

• 実装例(C++)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> ans{K};
  for (int n = 0; n < N; n++) {
    vector<int> nxt;
    for (int a : ans) {
      nxt.push_back(a / 2);
      nxt.push_back(a - a / 2);
    }
    ans = nxt;
  }
  int max = *max_element(begin(ans), end(ans));
  int min = *min_element(begin(ans), end(ans));
  cout << max - min << "\n";
  for (int i = 0; i < (int)ans.size(); i++) {
    cout << ans[i] << " \n"[i + 1 == (int)ans.size()];
  }
}