分数: 100 点
问题陈述
有 N \times M 在数轴上的石头,具有 M 标记的颜色 1 通过 M,和 N 每种颜色的石头。这里, N 是一个 偶数,和 M 是一个 奇数。在颜色为...的石头中 i, j左起第 3 块石头 (1 ≤ i ≤ M,\ 1 ≤ j ≤ N) 最初放置在坐标 (j-1) \times M + i颜色相同的石头无法区分。
你可以执行以下操作最多 (N+1) \times M 次:
选择两个相邻的石头,并按相同的顺序移动它们到任何空闲的相邻位置。
具体来说:
- 选择一个整数 x 这样 -10^9 \leq x \leq 10^9-1 并且在两个坐标上都有石头 x 和 x+1令位于的石头 x be A 和位于的石头 x+1 be B。删除 A 和 B 来自数轴。
- 选择一个整数 y 这样 -10^9 \leq y \leq 10^9-1 并且在两个坐标上都没有石头 y 和 y+1。放置 A at y 和 B at y+1.
你的目标是重新排列石头以满足以下两个条件:
- 所有石头都属于一个连续的整体。也就是说,存在一个整数 n 使得对于所有整数 x 满意 n \leq x \leq n + NM - 1,在坐标上恰好有一块石头 x.
- 另外,这些石头按颜色升序排列。具体来说,在颜色为 i, j左起第 3 块石头 (1 ≤ i ≤ M,\ 1 ≤ j ≤ N) 位于坐标处 n + (i-1) \times N + (j-1).
在这个问题的约束下,可以证明目标总是可以实现的。输出一个有效的操作序列以实现目标。你不需要最小化操作次数。
约束
- 2 \leq N \leq 1000
- 3 \leq M \leq 999
- N 是偶数
- M 是奇数
输入
输入按以下格式给出:
N M
输出
按以下格式输出解决方案:
K x_1 y_1 x_2 y_2 \vdots x_K y_K
在这里, K 是执行的操作次数,且 x_k, y_k\ (1 \leq k \leq K) 代表的值 x 和 y 选择于 k-第次操作。
输出必须满足以下约束条件:
- 0 \leq K \leq (N+1) \times M
- -10^9 \leq x_k, y_k \leq 10^9-1\ (1 \leq k \leq K)
如果有多个有效解,则输出其中任意一个。
示例输入 1
4 3
示例输出 1
13 3 13 10 3 12 10 6 12 4 6 1 4 13 14 14 14 14 999999999 999999999 -1000000000 9 13 5 9 -1000000000 5
最初,石头的摆放如下(. 表示一个空位)。最左边的坐标为 . is 0,最右边的坐标为 . is 15.
.123123123123...
前三次操作后,石头的排列如下:
.123123123123... ↓ .12..2312312331. ↓ .121223123..331. ↓ .12122312333..1.
最后,石头按如下方式重新排列:
...111122223333.
这种排列满足单一连续块且按颜色排序的条件。此外,操作次数最多为 (N + 1) \times M = 15,因此该输出是有效的。