310326: CF1816B. Grid Reconstruction
Description
Consider a $2 \times n$ grid, where $n$ is an even integer. You may place the integers $1, 2, \ldots, 2n$ on the grid, using each integer exactly once.
A path is a sequence of cells achieved by starting at $(1, 1)$, then repeatedly walking either downwards or to the right, and stopping when $(2, n)$ is reached. The path should not extend beyond the grid.
The cost of a path is the alternating sum of the numbers written on the cells in a path. That is, let the numbers written on the cells be $a_1, a_2, \ldots, a_k$ (in the order that it is visited), the cost of the path is $a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1}$.
Construct a way to place the integers $1, 2, \ldots, 2n$ on the grid, such that the minimum cost over all paths from $(1, 1)$ to $(2, n)$ is maximized. If there are multiple such grids that result in the maximum value, output any of them.
InputThe first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of test cases follows.
The first and the only line of each test case contains a single integer $n$ ($2 \leq n \leq 10^5$, $n$ is even) — the number of the columns in the grid.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
OutputFor each test case, output $2$ lines, each containing $n$ integers — the desired grid. If there are multiple solutions, output any of them.
ExampleInput3 2 4 6Output
3 2 1 4 8 2 6 4 1 5 3 7 11 5 9 1 7 3 6 10 2 8 4 12Note
In the first test case, there are only two paths from cell $(1, 1)$ to cell $(2, 2)$. Their costs are $3-1+4=6$ and $3-2+4=5$. Then the minimum cost is $5$, which is the maximum possible value.
In the second test case, there are four paths from cell $(1, 1)$ to cell $(2, 4)$. Their costs are $8-1+5-3+7=16$, $8-2+5-3+7=15$, $8-2+6-3+7=16$, and $8-2+6-4+7=15$. Then the minimum value is $15$, which is the maximum possible value.
Input
题意翻译
**题目描述** 在一个 $2×n$ 的网格中 （$n$ 为偶数），标记 $1,2,\ldots,2n$，但每个数只能被使用 $1$ 次。 某条路径是从 $(1,1)$ 开始的单元序列，随后不断地向下走或向右走，直到到达 $(2,n)$。注意：这条路径不能超出网格的边界。 通过这条路径的成本是这条路径所通过的单元格上的数字交替和，即，设路径上的数为 $a,a_1,a_2,\ldots,a_k$（它是第几个被标记到的，它的下标就是几），则通过这条路径的成本就是 $ a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1} $。 你需要求一个在网格中标记 $1,2,...,2n$ 的方案，最大化成本最小的路径的成本。如果有多个答案，你可以输出任意一个。本题中，每个测试点包含 $t$ 组数据。 **输入格式** 第一行包含 $t$（$t$ 是测试数据组数）。 随后的 $t$ 行，每行给出一个 $n$，表示网格的边长。 数据保证 $n\le10^5$。 **输出格式** 共 $2t$ 行，每组测试数据两行，每行包含 $n$ 个整数，表示所需的网格。如果有多个答案，你可以输出任意一个。 **说明/提示** 在第一组测试数据中，只有两条从 $(1,1)$ 到 $(2,2)$ 的路径，它们的成本分别是 $3-1+4=6$ 和 $3-2+4=5$，其中成本更小的方案是 $5$，这是最优的方案。 在第二组测试数据中，有四条从 $(1,1)$ 到 $(2,4)$ 的路径，它们的成本分别是 $8-1+5-3+7=16$，$8-2+5-3+7=15$，$8-2+6-3+7=16$ 和 $8-2+6-4+7=15$，其中成本最小的一种方案是 $15$，这是最优的方案。Output
这个问题是关于如何在一个2×n的网格上放置整数1, 2, ..., 2n，以便最大化从(1, 1)到(2, n)的所有路径中的最小成本。网格的每个单元恰好使用一次整数。路径是从(1, 1)开始，只能向下或向右移动，直到到达(2, n)。路径的成本是路径上单元格数字的交替和，即如果路径上的数字是a1, a2, ..., ak，则成本是a1 - a2 + a3 - a4 + ... = Σ ai * (-1)^(i+1)。需要构建一个放置整数的方式，使得所有路径的最小成本最大化。如果有多个这样的网格，输出其中一个。
输入数据格式：
第一行包含一个整数t（1 ≤ t ≤ 1000），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例只有一行，包含一个整数n（2 ≤ n ≤ 10^5，n是偶数）——网格中的列数。
保证所有测试用例的n之和不超过10^5。
输出数据格式：
对于每个测试用例，输出2行，每行包含n个整数——所需的网格。如果有多个解决方案，输出其中任何一个。
请注意，上述内容中的公式是用LaTeX格式编写的。题目大意： 这个问题是关于如何在一个2×n的网格上放置整数1, 2, ..., 2n，以便最大化从(1, 1)到(2, n)的所有路径中的最小成本。网格的每个单元恰好使用一次整数。路径是从(1, 1)开始，只能向下或向右移动，直到到达(2, n)。路径的成本是路径上单元格数字的交替和，即如果路径上的数字是a1, a2, ..., ak，则成本是a1 - a2 + a3 - a4 + ... = Σ ai * (-1)^(i+1)。需要构建一个放置整数的方式，使得所有路径的最小成本最大化。如果有多个这样的网格，输出其中一个。 输入数据格式： 第一行包含一个整数t（1 ≤ t ≤ 1000），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例只有一行，包含一个整数n（2 ≤ n ≤ 10^5，n是偶数）——网格中的列数。 保证所有测试用例的n之和不超过10^5。 输出数据格式： 对于每个测试用例，输出2行，每行包含n个整数——所需的网格。如果有多个解决方案，输出其中任何一个。 请注意，上述内容中的公式是用LaTeX格式编写的。