QOJ.ac

QOJ

시간 제한: 2 s 메모리 제한: 2048 MB 총점: 100

#15133. 魔法师的和谐过河

통계

有一条非常狭窄的小巷,两队魔术师想要从相反的两端穿过这条小巷。在两队之间只剩下一个能容纳一人的空间之前,他们是看不到对方队伍的。因为小巷非常狭窄,他们无法转身或向后走以避免摔倒。然而,作为魔术师,他们可以使用法术进行短距离传送,从而允许他们与另一个人擦肩而过。此外,为了维持秩序,同一队伍中的魔术师不能改变他们的相对顺序,因此他们不能使用这个法术来超越同一队伍的魔术师。

为了明确起见,我们假设第一队有 $n$ 个魔术师,从左侧开始,编号为 $1$ 到 $n$;第二队有 $m$ 个魔术师,从右侧开始,编号为 $n + 1$ 到 $n + m$。

这条狭窄的小巷共有 $n + m + 1$ 个位置。最左边的 $n$ 个位置被第一队占据,面向右;最右边的 $m$ 个位置被第二队占据,面向左。小巷的初始配置如下:$[1, 2, \dots, n, \text{space}, n + 1, n + 2, \dots, n + m]$。

当一个魔术师移动时,他必须遵循以下规则:

  • 如果他的正前方有一个空位,他可以走进那个空位。
  • 如果他的正前方是来自对方队伍的魔术师,且该魔术师的正后方是一个空位,他可以使用法术移动到那个空位。

最终,第一队将占据最右边的 $n$ 个位置,第二队将占据最左边的 $m$ 个位置。

为了帮助他们穿过小巷,请提供一个允许他们通过的移动策略。该策略将用一个数字序列 $a_1, a_2, \dots$ 来描述,其中 $a_i$ 表示在第 $i$ 步中,编号为 $a_i$ 的魔术师将移动到未被占据的空位。

如果存在多种策略,请输出字典序最小的一种。字典序是一种基于字母或数字顺序比较字符串或元素序列的方法。在本题的语境中,“字典序最小”的策略是指当策略被表示为数字序列时,在数值顺序上最先出现的策略。

更具体地:

  • 每个策略都表示为一个数字序列:$a_1, a_2, \dots$
  • 两个策略逐个元素进行比较:
    • 如果一个策略的第一个元素小于另一个策略的第一个元素,则第一个策略的字典序较小。
    • 如果第一个元素相等,则比较第二个元素,依此类推。

输入格式

第一行包含一个整数 $t$,表示测试用例的数量。对于接下来的 $t$ 行,每行包含两个整数 $n$ 和 $m$,分别表示第一队的魔术师人数和第二队的魔术师人数。

输出格式

输出 $t$ 行。第 $i$ 行应包含帮助第 $i$ 个测试用例中的魔术师穿过狭窄小巷的移动策略。如果存在多种策略,输出字典序最小的一种。

数据范围

  • $2 \le n \le 3000$
  • $2 \le m \le 3000$
  • $1 \le t \le 1000$
  • 所有测试用例中 $n$ 的总和不超过 $3000$。
  • 所有测试用例中 $m$ 的总和不超过 $3000$。

样例

输入样例 1

2
2 2
2 3

输出样例 1

2 3 4 2 1 3 4 1
2 3 4 2 1 3 4 5 2 1 5

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.