← 返回题目列表

AtCoder · ttpc2024_2_m

M. 七彩石分类

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

分数: 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 次:

选择两个相邻的石头,并按相同的顺序移动它们到任何空闲的相邻位置。
具体来说:

  1. 选择一个整数 x 这样 -10^9 \leq x \leq 10^9-1 并且在两个坐标上都有石头 x 和 x+1令位于的石头 x be A 和位于的石头 x+1 be B。删除 A 和 B 来自数轴。
  2. 选择一个整数 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,因此该输出是有效的。