← 返回题目列表

Codeforces · 2121/D

D. 1709之谜

中文机器翻译题面 查看原题

给定两个整数数组 $$$a_1, a_2, \ldots, a_n$$$ 和 $$$b_1, b_2, \ldots, b_n$$$。保证从 $$$1$$$ 到 $$$2 \cdot n$$$ 的每个整数恰好出现在其中一个数组中。

您需要执行一定数量的操作(可能为零),以便 两者 满足以下条件的 :

  • 对于每个 $$$1 \leq i \lt n$$$,它认为 $$$a_i \lt a_{i + 1}$$$ 和 $$$b_i \lt b_{i + 1}$$$。
  • 对于每个 $$$1 \leq i \leq n$$$,它认为 $$$a_i \lt b_i$$$。

在每个操作期间,您可以执行以下三个操作之一:

  1. 选择索引 $$$1 \leq i \lt n$$$ 并交换值 $$$a_i$$$ 和 $$$a_{i + 1}$$$。
  2. 选择索引 $$$1 \leq i \lt n$$$ 并交换值 $$$b_i$$$ 和 $$$b_{i + 1}$$$。
  3. 选择索引 $$$1 \leq i \leq n$$$ 并交换值 $$$a_i$$$ 和 $$$b_i$$$。

您不需要最小化操作次数,但总数不得超过$$$1709$$$。找到满足以下条件的任意操作序列 两者 满足以下条件的 条件。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 40$$$) — 数组 $$$a$$$ 和 $$$b$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2 \cdot n$$$)。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 2 \cdot n$$$)。

保证从 $$$1$$$ 到 $$$2 \cdot n$$$ 的每个整数出现在数组 $$$a$$$ 或数组 $$$b$$$ 中。

输出

对于每个测试用例,输出操作序列。

在每个测试用例的第一行,输出操作数$$$k$$$。请注意 $$$0 \leq k \leq 1709$$$。

在每个测试用例的以下 $$$k$$$ 行中,输出操作本身:

  • 如果要交换 $$$a_i$$$ 和 $$$a_{i + 1}$$$ 的值,请输出两个整数 $$$1$$$ 和 $$$i$$$。请注意 $$$1 \leq i \lt n$$$。
  • 如果要交换 $$$b_i$$$ 和 $$$b_{i + 1}$$$ 的值,请输出两个整数 $$$2$$$ 和 $$$i$$$。请注意 $$$1 \leq i \lt n$$$。
  • 如果要交换值 $$$a_i$$$ 和 $$$b_i$$$,请输出两个整数 $$$3$$$ 和 $$$i$$$。请注意 $$$1 \leq i \leq n$$$。

可以证明,在给定的约束下,解总是存在。

示例

输入
复制

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

输出
复制

0
1
3 1
1
2 1
1
3 2
9
3 1
3 2
3 3
1 1
2 1
2 2
1 2
1 1
2 1
6
2 2
1 1
1 2
2 1
3 1
3 2

注意

在第一个测试用例中,$$$a_1 \lt b_1$$$,因此不需要应用任何操作。

在第二个测试用例中,$$$a_1 \gt b_1$$$。应用操作后,这些值将被交换。

在第三个测试用例中,应用操作后,$$$a = [1, 3]$$$ 和 $$$b = [2, 4]$$$。

在第四个测试用例中,应用操作后,$$$a = [1, 2]$$$ 和 $$$b = [3, 4]$$$。