注意:问题 "Reversort" 和 "Reversort Engineering" 的题目描述主要部分相同,仅最后一段不同。这两个问题可以独立求解。
Reversort 是一种将不同整数列表按升序排序的算法。该算法基于 "Reverse"(翻转)操作。每次应用此操作都会翻转列表中某个连续部分。
该算法的伪代码如下:
Reversort(L): for i := 1 to length(L) - 1 j := position with the minimum value in L between i and length(L), inclusive Reverse(L[i..j])
经过 $i - 1$ 次迭代后,列表的前 $i - 1$ 个位置包含 $L$ 中最小的 $i - 1$ 个元素,且按升序排列。在第 $i$ 次迭代期间,该过程会翻转从第 $i$ 个位置到第 $i$ 个最小元素当前位置的子列表。这使得第 $i$ 个最小元素最终位于第 $i$ 个位置。
例如,对于一个包含 4 个元素的列表,该算法将执行 3 次迭代。以下是它处理 $L = [4, 2, 1, 3]$ 的过程:
- $i = 1, j = 3 \longrightarrow L = [1, 2, 4, 3]$
- $i = 2, j = 2 \longrightarrow L = [1, 2, 4, 3]$
- $i = 3, j = 4 \longrightarrow L = [1, 2, 3, 4]$
在我们架构上执行该算法,最昂贵的部分是 Reverse 操作。因此,我们衡量每次迭代代价的方式仅仅是传递给 Reverse 的子列表长度,即值 $j - i + 1$。整个算法的代价是每次迭代代价的总和。
在上面的例子中,迭代的代价依次为 3、1 和 2,总计为 6。
给定一个大小 $N$ 和一个代价 $C$。请找出一个包含 1 到 $N$ 之间不同整数的列表,使得应用 Reversort 后的代价恰好为 $C$,或者说明不存在这样的列表。
输入格式
第一行输入包含测试用例的数量 $T$。接下来 $T$ 行,每行描述一个测试用例,包含两个整数 $N$ 和 $C$,分别表示所需的列表大小和期望的代价。
输出格式
对于每个测试用例,如果不存在大小为 $N$ 且应用 Reversort 后代价恰好为 $C$ 的列表,则输出一行 Case #x: IMPOSSIBLE,其中 $x$ 是测试用例编号(从 1 开始)。否则,输出一行 Case #x: y1 y2 ... yN,其中 $x$ 是测试用例编号(从 1 开始),每个 $y_i$ 是 1 到 $N$ 之间的一个不同整数,代表该可能列表的第 $i$ 个元素。
如果存在多个解,你可以输出其中任意一个。(参见 FAQ 中 "What if a test case has multiple correct solutions?" 部分。)此关于多解的信息在 2021 竞赛的其余部分中将不会明确说明。
数据范围
$1 \le T \le 100$ $1 \le C \le 1000$
测试集 1(可见判定): $2 \le N \le 7$
测试集 2(可见判定): $2 \le N \le 100$
样例
样例输入 1
5 4 6 2 1 7 12 7 2 2 1000
样例输出 1
Case #1: 4 2 1 3 Case #2: 1 2 Case #3: 7 6 5 4 3 2 1 Case #4: IMPOSSIBLE Case #5: IMPOSSIBLE
说明
样例 #1 已在题目描述中说明。
在样例 #2 中,算法在建议的输出上仅运行了一次迭代。在那次迭代中,reverse 被应用于大小为 1 的子列表,因此其代价为 1。
在样例 #3 中,第一次迭代翻转了整个列表,代价为 7。此后,列表已经排序,但还有 5 次迭代,每次贡献 1 的代价。另一个有效的输出是 7 5 4 3 2 1 6。对于该输出,第一次迭代代价为 6,最后一次为 2,其余均为 1。
在样例 #4 中,Reversort 必然执行 6 次迭代,每次代价至少为 1,因此总代价不可能低至要求的值。