参议院撤离 - 题目

参议院会议厅发生了小火灾，需要进行疏散！

参议院会议厅内有一些参议员，每位参议员都属于 $N$ 个政党中的一个。这些政党以英语字母表的前 $N$ 个大写字母命名。

紧急出口一次最多可容纳两名参议员，因此在疏散的每一步中，你可以选择从会议厅中撤离一名或两名参议员。

参议院规则规定，会议厅内的参议员可以随时对任何法案进行投票，即使在疏散过程中也是如此！因此，必须以确保没有任何政党拥有绝对多数席位的方式疏散参议员。也就是说，在任何疏散步骤之后，绝不能出现某个政党的参议员人数超过会议厅内参议员总数一半的情况。

你能制定一个疏散计划吗？参议院正指望着你！

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含两行。第一行包含一个整数 $N$，表示政党的数量。第二行包含 $N$ 个整数 $P_1, P_2, \dots, P_N$，其中 $P_i$ 表示以字母表中第 $i$ 个字母命名的政党的参议员人数。

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是疏散计划。该计划必须是一系列以空格分隔的指令，按执行顺序排列，每条指令由一个或两个字符组成，代表每一步要疏散的参议员所属的政党。

保证至少存在一个有效的疏散计划。如果存在多个有效的疏散计划，你可以输出其中任何一个。

$1 \le T \le 50$。在疏散开始前，没有任何政党拥有绝对多数席位。 $1 \le P_i \le 1000$，对于所有 $i$。

小型数据集（测试集 1 - 可见）

$2 \le N \le 3$。所有 $P_i$ 之和 $\le 9$。

大型数据集（测试集 2 - 隐藏）

$2 \le N \le 26$。所有 $P_i$ 之和 $\le 1000$。

Case #1: AB BA
Case #2: AA BC C BA
Case #3: C C AB
Case #4: BA BB CA

样例输出展示了针对样例测试用例的一组答案。其他答案也可能是有效的。

在 Case #1 中，政党 A 和 B 各有两名参议员。如果我们每次从每个政党各撤离一名，在疏散完成前都能保持完美的平衡。

Case #2 的过程如下：初始在会议厅内：3 A, 2 B, 2 C。撤离 AA。剩余：1 A, 2 B, 2 C。撤离 BC。剩余：1 A, 1 B, 1 C。撤离 C。剩余：1 A, 1 B。撤离 AB。疏散完成！

注意，如果以 BC 开始疏散是无效的，因为这会留下 3 A, 1 B 和 1 C 在会议厅内；政党 A 将拥有绝对多数（5 人中有 3 人 = 60%）。

对于 Case #3，注意 CC AB 也是一个有效的答案，并且即使 C C AB 需要三个疏散步骤而不是两个，它也是有效的。

QOJ.ac