P11631 [CTS2025] 倾诉（暂无数据）

IOI 2025 中国国家队选拔 d1t1。

“在我们倾诉的时候，烦恼衰减了。倾诉者的难过一半交给了对方，另一半随着声 波还给了世界。烦恼就这样在人群里越传越弱，直到随风而逝。” 小 I 的小圈子里有 $n$ 个人，第 $i$ $(1 \le i \le n)$ 个人初始**有正整数** $a_i$ 的烦恼。 为了减轻大家的烦恼，小 I 组织了一次聊天活动，活动中 $n$ 个人按照编号从小到大 的顺序从左往右坐成一排。 时间有限，小 I 可以在活动中组织**不超过** $k$ 次倾诉。每次倾诉中，某个倾诉者 $p$ $(1 \le p \le n − 1)$ 向右手边的人 $p + 1$ 倾诉，这首先导致 $a_{p+1} \gets a_{p+1} + \frac{1}{2} a_p$，然后 $a_p \gets 0$，其中 $\gets$ 表示赋值。小 I 可以任意选择每次倾诉的倾诉者。注意编号为 $n$ 的人不会向其他人倾诉。 小 I 希望大家的烦恼尽可能少，于是他想知道：在活动过后，所有人最终烦恼的最大值最小是多少。 你需要输出答案的精确值。具体地，答案总能写成 $\frac{S}{2^n}$ 的形式，其中 $S$ 是一个不超过 $2^n \times \left(\max_{i=1}^n a_i\right)$ 的正整数。你需要输出 $S$ 的二进制表示。

**本题有多组测试数据**。输入的第一行一个整数 $T$，表示测试数据组数，接下来依次描述每组测试数据。 对于每组数据，第一行两个整数 $n, k$，分别表示人数和倾诉次数上限；第二行 $n$ 个正整数 $a_1, a_2, \cdots , a_n$ 描述初始每个人的烦恼值。

对于每组数据输出一行一个 $\texttt{01}$ 字符串，从高位到低位描述 $S$ 的二进制表示。你的输出不应该有前导零。

### 样例解释 #### 样例 $1$ 解释 对于第一组测试数据，最优策略为让第一个人倾诉。最终烦恼值为 $(0, 4.5, 1)$，故输出 $4.5 \times 2^3 = 36$ 的二进制表示 $\texttt{100100}$。 对于第二和第三组测试数据，最优策略为先让第二个人倾诉，再让第一个人倾诉。最终烦恼值为 $(0, 2.5, 2)$，故输出 $2.5 \times 2^3 = 20$ 的二进制表示 $\texttt{10100}$。 #### 样例 $2$ 解释 该组样例七个测试数据的答案分别为 $10, 10, 8, 5, 3.5, 2.75, 2.5$。 ### 数据范围 设 $\sum n$ 表示单个测试点中所有测试数据的 $n$ 的和。对于所有测试数据，保证 - $1 \le T \le 2 \times 10^4$， - $1 \le n, \sum n \le 2 \times 10^4$，$1 \le k \le 10^9$， - $\forall 1 \le i \le n, 1 \le a_i \le 10^6$。 | 子任务编号 | 分值 | $\sum n\le$ | $a_i\le$ | $k \ge$ | |:-:| :-:| :-: | :-: | :-: | | $1$ | $2 $ | $30 $ | $10^6$ | $1$ | | $2$ | $10$ | $200 $ | $10^6$ | $1$ | | $3$ | $13$ | $750 $ | $10^6$ | $1$ | | $4$ | $20$ | $2,500 $ | $10^6$ | $1$ | | $5$ | $17$ | $10^4$ | $10^4$ | $1$ | | $6$ | $16$ | $2 \times 10^4$ | $10^6$ | $10^9$ | | $7$ | $22$ | $2\times 10^4$ | $10^6$ | $1$ |