CF1816B.Grid Reconstruction
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Consider a 2×n grid, where n is an even integer. You may place the integers 1,2,…,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 a1,a2,…,ak (in the order that it is visited), the cost of the path is a1−a2+a3−a4+…=∑i=1kai⋅(−1)i+1 .
Construct a way to place the integers 1,2,…,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.
输入格式
The first line contains a single integer t ( 1≤t≤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≤n≤105 , 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 105 .
输出格式
For each test case, output 2 lines, each containing n integers — the desired grid. If there are multiple solutions, output any of them.
输入输出样例
输入#1
3 2 4 6
输出#1
3 2 1 4 8 2 6 4 1 5 3 7 11 5 9 1 7 3 6 10 2 8 4 12
说明/提示
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.