QOJ.ac

QOJ

时间限制: 10 s 内存限制: 1024 MB 总分: 18

#12446. Reversort 工程学

统计

注意:问题 "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]$ 的过程:

  1. $i = 1, j = 3 \longrightarrow L = [1, 2, 4, 3]$
  2. $i = 2, j = 2 \longrightarrow L = [1, 2, 4, 3]$
  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,因此总代价不可能低至要求的值。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.