# D - Least Unbalanced [문제 링크](https://atcoder.jp/contests/abc422/tasks/abc422_d) ## Problem Statement Let $N$ be a positive integer. Define the **imbalance** of a sequence $A=(A_1, A_2, \dots, A_{2^N})$ of non-negative integers of length $2^N$ as the non-negative integer value obtained by the following operation: * Initially, set $X=0$. * Perform the following series of operations $N$ times: * Update $X$ to $\max\!\bigl(X,\ \max(A)-\min(A)\bigr)$, where $\max(A)$ and $\min(A)$ denote the maximum and minimum values of sequence $A$, respectively. * Form a new sequence of half the length by pairing elements from the beginning two by two and arranging their sums. That is, set $A \gets (A_1 + A_2,\ A_3 + A_4,\ \dots,\ A_{\lvert A \rvert - 1} + A_{\lvert A \rvert})$. * The final value of $X$ is the imbalance. For example, when $N=2,\ A=(6, 8, 3, 5)$, the imbalance is $6$ through the following steps: * Initially, $X=0$. * The first series of operations is as follows: * Update $X$ to $\max\!\bigl(X,\ \max(A)-\min(A)\bigr)=\max(0,\ 8-3)=5$. * Set $A$ to $(6+8,\ 3+5)=(14,\ 8)$. * The second series of operations is as follows: * Update $X$ to $\max\!\bigl(X,\ \max(A)-\min(A)\bigr)=\max(5,\ 14-8)=6$. * Set $A$ to $(14+8)=(22)$. * Finally, $X=6$. You are given a non-negative integer $K$. Among all sequences of non-negative integers of length $2^N$ with sum $K$, construct a sequence that minimizes the imbalance. ## Constraints * $1 \le N \le 20$ * $0 \le K \le 10^{9}$ * $N$ and $K$ are integers. ## Input The input is given from Standard Input in the following format: $N$ $K$ ## Output Let $B=(B_1, B_2, \dots, B_{2^N})$ be a sequence with minimum imbalance. Let $U$ be the imbalance of $B$. Output a solution in the following format: $U$ $B_1$ $B_2$ $\dots$ $B_{2^N}$ If there are multiple solutions, any of them will be considered correct. ## 풀이 직접 n번 반복하며 절반으로 쪼개보면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); ll n, k; cin >> n >> k; vector<ll> A = {k}; while(n--) { vector<ll> nextA; for(ll e : A) { nextA.push_back(e/2); nextA.push_back((e+1)/2); } A = nextA; } cout << *max_element(A.begin(), A.end()) - *min_element(A.begin(), A.end()) << '\n'; for(ll e : A) cout << e << ' '; } ```