← 返回题目列表

Codeforces · 1552/E

E. 颜色和间隔

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

数字 $$$1, \, 2, \, \dots, \, n \cdot k$$$ 用 $$$n$$$ 颜色着色。这些颜色的索引为 $$$1, \, 2, \, \dots, \, n$$$。对于每个 $$$1 \le i \le n$$$,正好有 $$$k$$$ 个数字,颜色为 $$$i$$$。

设$$$[a, \, b]$$$表示$$$a$$$和$$$b$$$之间的整数区间,即集合$$$\{a, \, a + 1, \, \dots, \, b\}$$$。您必须选择 $$$n$$$ 间隔 $$$[a_1, \, b_1], \, [a_2, \, b_2], \, \dots, [a_n, \, b_n]$$$,这样:

- 对于每个 $$$1 \le i \le n$$$,它包含 $$$1 \le a_i < b_i \le n \cdot k$$$;
- 对于每个 $$$1 \le i \le n$$$,数字 $$$a_i$$$ 和 $$$b_i$$$ 用颜色 $$$i$$$ 着色;
- 每个数字 $$$1 \le x \le n \cdot k$$$ 最多属于 $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ 区间。

我们可以证明这样一组区间在给定的约束下总是存在。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 100$$$, $$$2 \le k \le 100$$$) — 颜色数量和每种颜色出现的次数。

第二行包含 $$$n \cdot k$$$ 整数 $$$c_1, \, c_2, \, \dots, \, c_{nk}$$$ ($$$1 \le c_j \le n$$$),其中 $$$c_j$$$ 是数字 $$$j$$$ 的颜色。可以保证,对于每个 $$$1 \le i \le n$$$,它对于 $$$k$$$ 不同索引 $$$j$$$ 持有 $$$c_j = i$$$。

输出

输出 $$$n$$$ 行。第 $$$i$$$ 行应包含两个整数 $$$a_i$$$ 和 $$$b_i$$$。

如果有多个有效的间隔选择,则输出任意一个。

示例

输入 #1

4 3
2 4 3 1 1 4 2 3 2 1 3 4

输出 #1

4 5
1 7
8 11
6 12

输入 #2

1 2
1 1

输出 #2

1 2

输入 #3

3 3
3 1 2 3 2 1 2 1 3

输出 #3

6 8
3 7
1 4

输入#4

2 3
2 1 1 1 2 2

输出#4

2 3
5 6

注意

在第一个样本中,每个数字最多可以包含在 $$$\left\lceil \frac{4}{3 - 1} \right\rceil = 2$$$ 个间隔中。输出如下图所示:

在第二个样本中,唯一要选择的区间被强制为 $$$[1, \, 2]$$$,并且每个数字确实最多包含在 $$$\left\lceil \frac{1}{2 - 1} \right\rceil = 1$$$ 区间中。

在第三个样本中,每个数字最多可以包含在 $$$\left\lceil \frac{3}{3 - 1} \right\rceil = 2$$$ 间隔中。输出如下图所示: