P13145 [GCJ 2018 #2] Falling Balls

某种玩具由一个有 $2$ 列或更多列、$1$ 行或更多行的网格组成，网格的每个格子中要么放有一个 $\backslash$ 斜坡，要么放有一个 $/$ 斜坡，要么为空。最左边和最右边的两列始终为空，最底下一行也始终为空。小球会从最顶上一行的每一列各投放一个，并垂直下落，遇到斜坡会滑动。为了防止小球卡住，任意一个放有 $\backslash$ 斜坡的格子左侧，绝不会紧挨着一个放有 $/$ 斜坡的格子。 当一个小球从顶行落下时，它的移动规则如下： - 如果小球当前在一个空格子中，则会直接落到正下方的格子，除非已经在最底行，此时小球不再移动。 - 如果小球当前在一个放有 $\backslash$ 斜坡的格子中，则会落到右下方的格子。 - 如果小球当前在一个放有 $/$ 斜坡的格子中，则会落到左下方的格子。 为了完整展示这个机制，用户会在每一列的顶行各投放一个小球。小球之间互不影响，一个格子中可以有多个小球。 你的朋友有这样一个玩具，列数为 $C$，行数未知。他在每一列的顶行各投放了一个小球，等所有小球都停止移动后，统计了每个底行格子里最终有多少个小球，并把这个结果告诉了你……但你怀疑他可能记错了。你能否构造出一个满足这些结果的布局，并且使用尽可能少的行数？或者判断根本不存在这样的布局？ 例如，如果你朋友报告的底行结果是 $3\ 0\ 0\ 2\ 0\ 1$，一种可能的解法如下（注意不要求斜坡数量最少，也不要求每个斜坡都必须影响小球的路径）： ``` ./\\... ./\.\/. ....... ``` 下图展示了小球在该网格中的下落路径： 

第一行输入测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据第一行为一个整数 $C$，表示朋友的玩具有多少列。接下来一行有 $C$ 个整数 $B_i$，第 $i$ 个整数表示朋友统计的底行从左到右第 $i$ 个格子里最终有多少个小球。

对于每组测试数据，输出一行 `Case #x: y`，其中 $x$ 是测试编号（从 $1$ 开始），$y$ 是你构造的布局所需的最少行数，或者如果不存在这样的布局则输出 `IMPOSSIBLE`。如果 $y$ 不是 `IMPOSSIBLE`，则接下来输出 $y$ 行，依次表示你构造的玩具布局的每一行，从上到下。用 `.` 表示空格子，`\` 或 `/` 分别表示对应的斜坡。布局必须满足题目中的所有规则。

**样例解释** 注意，最后一个样例不会出现在测试集 1 中。 对于样例 1，唯一的有效解法如下（必须至少有一行，增加更多行会导致行数不最少。底行不能有任何斜坡）： ``` .... ``` 对于样例 2，没有办法阻止最左边的小球直接落到底部，因为那一列不能放斜坡。 样例 3 就是题目描述最后给出的例子。注意，下面这个布局是非法的，因为它有多余的行数，左、右边界和底行都放了斜坡，而且出现了 $/$ 斜坡左侧紧挨着 $\backslash$ 斜坡的情况： ``` \\..\/ ../.\/ ./../. ..../. ``` **数据范围** - $1 \leq T \leq 100$。 - $0 \leq B_i \leq C$，对所有 $i$ 均成立。 - 所有 $B_i$ 之和等于 $C$。 **测试集 1（5 分，公开）** - $2 \leq C \leq 5$。 **测试集 2（12 分，隐藏）** - $2 \leq C \leq 100$。 由 ChatGPT 4.1 翻译