/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
N を正整数とします。長さ 2^N の非負整数列 A=(A_1, A_2, \dots, A_{2^N}) の アンバランスさ を次の操作によって得られる非負整数値として定義します。
- はじめ、X=0 とする。
- 次の一連の操作を N 回行う。
- X を \max(X, \max(A) - \min(A)) に更新する。ここで \max(A) および \min(A) は数列 A の最大値と最小値を意味する。
- 先頭から順に 2 つずつ要素を組にして、それらの和を並べることでできる長さが A の半分の数列を、新たな A とする。すなわち、A \gets (A_1 + A_2, A_3 + A_4, \dots, A_{\vert A \vert - 1} + A_{\vert A \vert}) とする。
- 最終的な X をアンバランスさとする。
例えば N=2, A=(6, 8, 3, 5) は以下の手順によりアンバランスさが 6 であるとわかります。
- はじめ、X=0 である。
- 1 回目の一連の操作は次の通りである。
- X を \max(X, \max(A) - \min(A)) = \max(0, 8 - 3) = 5 に更新する。
- A を (6+8, 3+5) = (14, 8) とする。
- 2 回目の一連の操作は次の通りである。
- X を \max(X, \max(A) - \min(A)) = \max(5, 14 - 8) = 6 に更新する。
- A を (14 + 8) = (22) とする。
- 最終的に X=6 となる。
非負整数 K が与えられます。長さ 2^N の非負整数列であって総和が K であるものの中で、アンバランスさが最小値を取る数列を構成してください。
制約
- 1 \leq N \leq 20
- 0 \leq K \leq 10^9
- N, K は整数
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
アンバランスさが最小値を取る数列を B=(B_1,B_2,\dots,B_{2^N}) とする。B のアンバランスさを U とする。この時、以下の形式で答えを出力せよ。
U
B_1 B_2 \dots B_{2^N}
答えが複数ある場合は、どれを出力しても正答とみなされる。
入力例 1
1 11
出力例 1
1 5 6
(5, 6) はアンバランスさが 1 の数列で、これが条件を満たす数列のうちアンバランスさが最小の数列です。
入力例 2
3 56
出力例 2
0 7 7 7 7 7 7 7 7
Score : 400 points
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(X, \max(A) - \min(A)), 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_{\vert A \vert - 1} + A_{\vert A \vert}).
- 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(X, \max(A) - \min(A)) = \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(X, \max(A) - \min(A)) = \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 \leq N \leq 20
- 0 \leq K \leq 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.
Sample Input 1
1 11
Sample Output 1
1 5 6
(5, 6) is a sequence with imbalance 1, which is the minimum imbalance among sequences satisfying the condition.
Sample Input 2
3 56
Sample Output 2
0 7 7 7 7 7 7 7 7