← 返回题目列表

Codeforces · 1968/E

E. 细胞排列

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

给你一个整数$$$n$$$。您在网格 $$$n\times n$$$ 中选择 $$$n$$$ 个单元格 $$$(x_1,y_1), (x_2,y_2),\dots,(x_n,y_n)$$$,其中 $$$1\le x_i\le n$$$ 和 $$$1\le y_i\le n$$$。

令 $$$\mathcal{H}$$$ 为任意一对像元之间的不同曼哈顿距离的集合。您的任务是最大化 $$$\mathcal{H}$$$ 的大小。注释中给出了集合及其构造的示例。

如果存在多个解,则允许输出任何一个。

像元 $$$(x_1,y_1)$$$ 和 $$$(x_2,y_2)$$$ 之间的曼哈顿距离等于 $$$|x_1-x_2|+|y_1-y_2|$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 50$$$) — 测试用例的数量。

以下 $$$t$$$ 行中的每一行都包含一个整数 $$$n$$$ ($$$2\le n\le 10^3$$$)。

输出

对于每个测试用例,输出 $$$n$$$ 点,使 $$$\mathcal{H}$$$ 的大小最大化。没有必要在每个测试用例的答案末尾输出空行。

示例

输入 #1

5
2
3
4
5
6

输出 #1

1 1
1 2

2 1
2 3
3 1

1 1
1 3
4 3
4 4

1 1
1 3
1 4
2 1
5 5

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

注意

在第一个测试用例中,我们有 $$$n=2$$$。一种可能的安排是:

单元格位于 $$$(1,1)$$$ 和 $$$(1,2)$$$ 中的排列。

在第二个测试用例中,我们有 $$$n=3$$$。最优的安排是:

单元格位于 $$$(2,1)$$$、$$$(2,3)$$$ 和 $$$(3,1)$$$ 中的排列。

$$$\mathcal{H}$$$=$$$\{|2-2|+|1-1|,|2-2|+|3-3|,|3-3|+|1-1|,|2-2|+|1-3| ,|2-3|+|1-1|,|2-3|+|3-1|\}$$$=$$$\{0,0,0,2,1,3\}$$$=$$$\{0,1,2,3\}$$$。

对于$$$n=4$$$,可能的安排是:

对于$$$n=5$$$,可能的安排是:

对于$$$n=6$$$,可能的安排是: